Splittings and Ramsey properties of permutation classes
From MaRDI portal
Abstract: We say that a permutation p is 'merged' from permutations q and r, if we can color the elements of p red and blue so that the red elements are order-isomorphic to q and the blue ones to r. A 'permutation class' is a set of permutations closed under taking subpermutations. A permutation class C is 'splittable' if it has two proper subclasses A and B such that every element of C can be obtained by merging an element of A with an element of B. Several recent papers use splittability as a tool in deriving enumerative results for specific permutation classes. The goal of this paper is to study splittability systematically. As our main results, we show that if q is a sum-decomposable permutation of order at least four, then the class Av(q) of all q-avoiding permutations is splittable, while if q is a simple permutation, then Av(q) is unsplittable. We also show that there is a close connection between splittings of certain permutation classes and colorings of circle graphs of bounded clique size. Indeed, our splittability results can be interpreted as a generalization of a theorem of Gy'arf'as stating that circle graphs of bounded clique size have bounded chromatic number.
Recommendations
Cites work
- scientific article; zbMATH DE number 2186865 (Why is no real title available?)
- scientific article; zbMATH DE number 3823785 (Why is no real title available?)
- scientific article; zbMATH DE number 3661342 (Why is no real title available?)
- scientific article; zbMATH DE number 3536154 (Why is no real title available?)
- scientific article; zbMATH DE number 1943960 (Why is no real title available?)
- Embedding dualities for set partitions and for relational structures
- For graphs there are only four types of hereditary Ramsey classes
- Generalized pigeonhole properties of graphs and oriented graphs
- Graphs with Monochromatic Complete Subgraphs in Every Edge Coloring
- Partially well-ordered closed sets of permutations
- Partitions and indivisibility properties of countable dimensional vector spaces
- Pattern avoidance classes and subpermutations
- Ramsey Classes and Homogeneous Structures
- Ramsey properties of permutations
- Ramsey-type properties of relational structures
- Simple permutations and algebraic generating functions
- Simple permutations and pattern restricted permutations
- Sur l'extension aux relations de quelques propriétés des ordres
- The On-Line Encyclopedia of Integer Sequences
- The age of a relational structure
- The profile of relations
- Theory of relations. Transl. from the French by P. Clote
- Upper bounds for the Stanley-Wilf limit of 1324 and other layered patterns
- Wreath products of permutation classes
Cited in
(9)- Composability of permutation classes
- Generalized coloring of permutations
- Generalized Coloring of Permutations
- Unsplittable classes of separable permutations
- Splittability and 1-amalgamability of permutation classes
- On the growth of merges and staircases of permutation classes
- The relation between composability and splittability of permutation classes
- Ramsey-type and amalgamation-type properties of permutations
- Deflatability of permutation classes
This page was built for publication: Splittings and Ramsey properties of permutation classes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q477770)
