2023/08/06 by Bonnet, Édouard, Bourneuf, Romain, Geniet, Colin +1 · 1 citation
#05A05 #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #G.2.1 #Logic in Computer Science (cs.LO)
paper · doi:10.48550/arxiv.2308.02981
We show that for any permutation π there exists an integer kπ such that every permutation avoiding π as a pattern is a product of at most kπ separable permutations. In other words, every strict class \mathcal C of permutations is contained in a bounded power of the class of separable permutations. This factorisation can be computed in linear time, for any fixed π. The central tool for our result is a notion of width of permutations, introduced by Guillemot and Marx [SODA '14] to efficiently detect patterns, and later generalised to graphs and matrices under the name of twin-width. Specifically, our factorisation is inspired by the decomposition used in the recent result that graphs with bounded twin-width are polynomially χ-bounded. As an application, we show that there is a fixed class \mathcal C of graphs of bounded twin-width such that every class of bounded twin-width is a first-order transduction of \mathcal C.