An Erd\H{o}s--Hajnal analogue for permutation classes
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$.
| Autor principal: | |
|---|---|
| Formato: | Artículo |
| Lenguaje: | English |
| Publicado: |
Discrete Mathematics & Theoretical Computer Science
2016-03-01
|
| Colección: | Discrete Mathematics & Theoretical Computer Science |
| Materias: | |
| Acceso en línea: | https://dmtcs.episciences.org/1328/pdf |