## Vatter, Vincent - An Erdős--Hajnal analogue for permutation classes

dmtcs:1417 - Discrete Mathematics & Theoretical Computer Science, March 24, 2016, Vol. 18 no. 2, Permutation Patterns 2015
An Erdős--Hajnal analogue for permutation classes

Authors: Vatter, Vincent

Let $\mathcal{C}$ be a permutation class that does not contain all layered permutations or all colayered permutations. We prove that there is a constant $c$ such that every permutation in $\mathcal{C}$ of length $n$ contains a monotone subsequence of length $cn$.

Source : oai:arXiv.org:1511.01076
Volume: Vol. 18 no. 2, Permutation Patterns 2015
Section: Permutation Patterns
Published on: March 24, 2016
Submitted on: March 24, 2016
Keywords: Mathematics - Combinatorics