Vincent Vatter
-
An Erdős--Hajnal analogue for permutation classes
dmtcs:1328 -
Discrete Mathematics & Theoretical Computer Science,
March 24, 2016,
Vol. 18 no. 2, Permutation Patterns 2015
-
https://doi.org/10.46298/dmtcs.1328An Erdős--Hajnal analogue for permutation classesArticle
Authors: Vincent Vatter
NULL
Vincent Vatter
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$.
Volume: Vol. 18 no. 2, Permutation Patterns 2015
Section: Permutation Patterns
Published on: March 24, 2016
Imported on: March 24, 2016
Keywords: Mathematics - Combinatorics
Funding:
Source : OpenAIRE Graph- The Structure of Permutation Classes; Funder: National Science Foundation; Code: 1301692