An Erdős--Hajnal analogue for permutation classesArticle
Authors: Vincent Vatter
NULL
Vincent Vatter
Let 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 C of length n contains a
monotone subsequence of length cn.