Splittings and Ramsey properties of permutation classes

DOI10.1016/J.AAM.2014.10.003zbMATH Open1304.05146arXiv1307.0027OpenAlexW2964309395MaRDI QIDQ477770FDOQ477770

Authors: Vít Jelínek, Pavel Valtr 

Publication date: 9 December 2014

Published in: Advances in Applied Mathematics (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1307.0027

Recommendations

• Unsplittable classes of separable permutations
• The relation between composability and splittability of permutation classes
• Splittability and 1-amalgamability of permutation classes
• Ramsey-type and amalgamation-type properties of permutations
• Composability of permutation classes

zbMATH Keywords

Ramsey theorypermutation classsplittability

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Ramsey theory (05D10)

Cites Work

• The On-Line Encyclopedia of Integer Sequences
• Theory of relations. Transl. from the French by P. Clote
• Sur l'extension aux relations de quelques propriétés des ordres
• Upper bounds for the Stanley-Wilf limit of 1324 and other layered patterns
• For graphs there are only four types of hereditary Ramsey classes
• Ramsey Classes and Homogeneous Structures
• Ramsey properties of permutations
• Title not available (Why is that?)
• Partially well-ordered closed sets of permutations
• Graphs with Monochromatic Complete Subgraphs in Every Edge Coloring
• Simple permutations and pattern restricted permutations
• Title not available (Why is that?)
• Pattern avoidance classes and subpermutations
• Title not available (Why is that?)
• Ramsey-type properties of relational structures
• The age of a relational structure
• Generalized pigeonhole properties of graphs and oriented graphs
• Wreath products of permutation classes
• Simple permutations and algebraic generating functions
• Title not available (Why is that?)
• Title not available (Why is that?)
• The profile of relations
• Partitions and indivisibility properties of countable dimensional vector spaces
• Embedding dualities for set partitions and for relational structures

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

Uses Software

• OEIS

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)