\[
\newcommand{\Av}{\operatorname{Av}}
\newcommand{\Grid}{\operatorname{Grid}}
\newcommand{\C}{\mathcal{C}}
\newcommand{\D}{\mathcal{D}}
\newcommand{\st}{\::\:}
\]
Let $\mathcal{C}$ be a permutation class that does not contain all layered permutations or all colayered permutations. We prove that every permutation in $\mathcal{C}$ contains a monotone subsequence of linear size.
Ramsey's Theorem tells us that every graph on $n$ vertices has a clique or independent set of size at least a constant times $\log n$. In 1989, Erdős and Hajnal conjectured that one can do much better when avoiding a fixed induced subgraph:
The Erdős–Hajnal Conjecture
For every graph $H$ there is a constant $\delta\ge0$ such that every graph on $n$ vertices which does not contain $H$ as an induced subgraph has a clique or independent set of size at least $n^\delta$.
We refer to Chudnovsky's survey for an account of the progress that has been made toward the Erdős–Hajnal Conjecture. Here we investigate a version of this conjecture for permutations. In this context, the analogue of the induced subgraph order is the permutation pattern order and the analogues of cliques and independent sets are decreasing and increasing subsequences, respectively. Thus the naive translation of the Erdős–Hajnal Conjecture to permutations is well known to hold with $\delta=1/2$:
The Erdős–Szekeres Theorem
Every permutation of length at least $(k-1)(\ell-1)+1$ contains either a decreasing subsequence of length $k$ or an an increasing subsequence of length $\ell$.
We instead ask for a stronger conclusion. A *permutation class* is a downset of permutations under the containment order. We show () that unless a permutation class contains all layered permutations or all colayered permutations, its members contain monotone subsequences of linear size.
The Erdős–Szekeres Theorem is best possible in that there are permutations of length $(k-1)(\ell-1)$ which have neither decreasing subsequences of length $k$ nor increasing subsequences of length $\ell$. Focusing on the case $k=\ell$, we call a permutation of length $k^2$ *Erdős–Szekeres extremal* if it does not contain a monotone subsequence of length $k+1$. If follows from the Robinson–Schensted correspondence and the Hook Length Formula that the number of Erdős–Szekeres extremal permutations of length $k^2$ is
\[\left(\frac {(k^2)!} {1^1\cdot 2^2\cdot 3^3\cdots k^k\cdot (k+1)^{k-1}\cdot (k+2)^{k-2}\cdots (2k-1)^1} \right)^2,
\]
sequence A079402 in the OEIS . One of the earliest references to this formula is Stanley's *Monthly* solution from 1969. There has also been some recent interest in these permutations. In particular, Romik computed the limit shape of Erdős–Szekeres extremal permutations. Additional results in this direction have been obtained by Kim , Pittel and Romik , and Su .
The layered permutation $321\ 654\ 987=\oplus^3 (321)$ and the colayered permutation $789\ 456\ 123=\ominus^3 (123)$.
Despite the fact that there are a great many extremal Erdős–Szekeres permutations, we need to define only two families, the *layered* and *colayered* extremal Erdős–Szekeres permutations, of which examples are plotted in . It is convenient to use the *sum* and *skew sum* operations in defining these permutations, which can be defined pictorially as below.
We use the symbols $\oplus^k$ and $\ominus^k$ to denote repeated sums and skew sums, respectively, so the extremal Erdős–Szekeres layered permutation of length $k^2$ is
\[\oplus^k (k\cdots 21) = \underbrace{(k\cdots 21)\oplus\cdots\oplus (k\cdots 21)}_{\text{ $k$ summands}}.
\]
We show that these two families of extremal permutations are the only obstructions preventing a class from having a linear bound on monotone subsequences:
Let $\C$ be a permutation class that does not contain the class of layered permutations or the class of colayered permutations. There is a constant $c>0$ such that every permutation of length $n$ in $\C$ contains a monotone subsequence of length at least $cn$.
One special case of is quite easy. By the folklore result that every permutation avoiding $k\cdots 21$ can be written as the union of $k-1$ increasing sequences (which can also be viewed as a consequence of Greene's Theorem , we obtain the following.
Let $\C$ be a permutation class that does not contain $k\cdots 21$ (or, by symmetry, $12\cdots k$). Then every permutation of length $n$ in $\C$ contains a monotone subsequence of length at least $n/(k-1)$.
To establish we first recall some results on transversals of (nonhomogeneousThere is also a homogeneous case, for which we refer to ) $d$-intervals (although we only appeal to the case $d=2$ in what follows). Let $L_1$, $\dots$, $L_d$ be disjoint copies of the real line. A $d$-interval $I$ is a nonempty subset of $L_1\cup\cdots\cup L_d$ such that each *component* $I\cap L_i$ is either empty or a closed interval. The *packing number* of a set $\mathfrak{I}$ of $d$-intervals is the maximum number of pairwise disjoint elements of $\mathfrak{I}$, and this quantity is denoted $\nu(\mathfrak{I})$. A subset of $L_1\cup\cdots \cup L_d$ which intersects every member of $\mathfrak{I}$ is called a *transversal* of $\mathfrak{I}$ and the minimum size of a transversal of $\mathfrak{I}$ is its *transversal number*, $\tau(\mathfrak{I})$.
A set of $2$-intervals (left) arising from a set of axis-parallel rectangles (right).
An example of a set of $2$-intervals is shown on the left of . In this example, the two copies of the real line are $L_x$ and $L_y$ and the $2$-intervals are $\mathfrak{I}=\{I_1,I_2,I_3\}$. We have $\nu(\mathfrak{I})=1$ because the $2$-intervals are pairwise intersecting, while $\tau(\mathfrak{I})=2$ because $2$ points of $L_x\cup L_y$ are required to intersect each of $I_1$, $I_2$, and $I_3$.
It is trivial to see that $\tau(\mathfrak{I})\ge \nu(\mathfrak{I})$. In the other direction, building on and improving work of Gyárfás and Lehel and Károlyi and Tardos , Tardos established the following.
Tardos
For every system $\mathfrak{I}$ of $2$-intervals, $\tau(\mathfrak{I})\le 2\nu(\mathfrak{I})$.
Note that the bound in is best possible given the example from .
Henceforth we adopt a geometric viewpoint of permutations where a permutation $\pi$ is identified with its *plot*, the set of points $\{(i,\pi(i))\}$ in the plane. Given two intervals $X$ and $Y$ of real numbers, we denote by $X\times Y$ the axis-parallel rectangle consisting of the points $\{(x,y)\st x\in X, y\in Y\}$. We further define $\pi(X\times Y)$ to be the subpermutation of $\pi$ formed by the entries of $\pi$ whose indices lie in $X$ and values lie in $Y$.
Given a set of closed axis-parallel rectangles $\mathfrak{R}$ we can naturally associate to it a set $\mathfrak{I}$ of $2$-intervals in the following manner. Let $L_x$ and $L_y$ be disjoint copies of the real line. For each $R\in\mathfrak{R}$ we create a $2$-interval $I_R$ such that $I_R\cap L_x$ is the projection of $R$ onto the $x$-axis and $I_R\cap L_y$ is the projection of $R$ onto the $y$-axis. The set of three rectangles shown on the right of corresponds in this manner to the set of $2$-intervals shown on the left of the figure.
We say that two rectangles are *independent* if both their $x$- and $y$-axis projections are disjoint. A set of rectangles is said to be independent if they are pairwise independent, and we define the *independence number* of a set of axis-parallel rectangles to be the size of the largest independent set of rectangles it contains.
It follows readily that if $\mathfrak{R}$ is a set of closed axis-parallel rectangles and $\mathfrak{I}$ is the corresponding set of $2$-intervals then the independence number of $\mathfrak{R}$ is equal to the packing number of $\mathfrak{I}$. Therefore shows that $\mathfrak{I}$ has a transversal of size at most $2\nu(\mathfrak{I})$. That is, there is a set of at most $2\nu(\mathfrak{I})$ points of $L_x\cup L_y$ which intersect every $2$-interval in $\mathfrak{I}$. We want to convert this transversal of $\mathfrak{I}$ into a set of vertical and horizontal lines that *slice* (i.e., intersect the interior) of every rectangle in $\mathfrak{R}$, but we must be careful because the transversal is allowed to contain endpoints of $2$-intervals. Thus given a transversal $T\subseteq L_x\cup L_y$ we associate to it a set of vertical and horizontal lines $\mathcal{L}_T$ in the following way: if $t\in T$ is from $L_x$ we associate the two vertical lines $x=t\pm\epsilon$ while if $t\in T$ is from $L_y$ we associate the two horizontal lines $y=t\pm\epsilon$ where $\epsilon\gt0$ is a small constant (depending on $\mathfrak{R}$). These are the dotted lines shown in . This construction yields the following result.
If a finite collection $\mathfrak{R}$ of axis-parallel rectangles has independence number at most $m$ then there is a collection of $4m$ vertical and horizontal lines which slice every rectangle in $\mathfrak{R}$.
We need one more definition. An *increasing sequence* of rectangles is a sequence $R_1,\dots,R_m$ of independent rectangles such that $R_{i+1}$ lies above and to the right of $R_i$ for all $i$. *Decreasing sequences* of rectangles are defined analogously. We are now ready to prove .
Proof of :
Let $\C$ be a permutation class which does not contain the class of layered permutations or the class of colayered permutations. Thus there is an integer $k$ such that $\C$ contains neither $\oplus^k (k\cdots 21)$ nor $\ominus^k (12\cdots k)$. Now choose a permutation $\pi\in\C$ and let $\mathfrak{R}_\pi$ denote the collection of all axis-parallel rectangles $R$ such that $\pi(R)$ contains both $k\cdots 21$ and $12\cdots k$. If $\mathfrak{R}_\pi$ were to contain an independent set of $(k-1)^2+1$ rectangles then the Erdős–Szekeres Theorem would imply that $\mathfrak{R}_\pi$ contained an increasing or decreasing sequence of $k$ rectangles, but that would imply that $\pi$ (and hence also $\C$) contained $\oplus^k (k\cdots 21)$ or $\ominus^k (12\cdots k)$, a contradiction. Thus the independence number of $\mathfrak{R}_\pi$ is at most $(k-1)^2$.
now shows that there is a collection of at most $4(k-1)^2$ vertical and horizontal lines which slice every rectangle in $\mathfrak{R}_\pi$. These lines divide the plot of $\pi$ into a $t\times u$ grid of unsliced regions for integers $t$ and $u$ satisfying $t+u\le 4(k-1)^2+2$. Moreover, each unsliced region avoids either $k\cdots 21$ or $12\cdots k$ and thus can be expressed as the union of $k-1$ increasing or decreasing permutations by . All of the entries of $\pi$ in regions avoiding $k\cdots 21$ can be expressed as the union of at most $(t+u-1)(k-1)\le 4k^3$ increasing permutations while the entries lying in regions avoiding $12\cdots k$ can be expressed as the union of the same number of decreasing permutations. Therefore $\pi$ itself can be expressed as the union of at most $8k^3$ monotone permutations and thus $\pi$ must contain a monotone subsequence of length at least $n/8k^3$, proving the theorem.
In the language of generalized grid classes introduced in Vatter , the proof of shows that all permutation classes that do not contain the layered or colayered permutations are $\Av(k\cdots 21)\cup\Av(12\cdots k)$-griddable. In fact, this follows from Theorem 3.1, though the bounds given in the proof above are better than that theorem gives.
can also be interpreted in the context of splittability, which has recently been studied in general by Jelínek and Valtr . Given two permutation classes $\C$ and $\D$, their *merge*, $\C\odot\D$, consists of those permutations whose entries can be partitioned into two subsequences, one order isomorphic to a permutation in $\C$ and the other order isomorphic to a permutation in $\D$. Thus shows that every class which does not contain the layered or colayered classes can be expressed as the merge of a finite number of monotone classes (i.e., classes of the form $\Av(21)$ or $\Av(12)$). Note that the converse---if a class does contain all layered or colayered permutations then it is not the merge of a finite number of monotone classes---holds trivially. The proof of also gives a bound on how many monotone classes are required:
If a permutation class avoids both $\oplus^k (k\cdots 21)$ and $\ominus^k (12\cdots k)$ then it can be expressed as the merge of at most $8k^3$ monotone classes.
* M. Chudnovsky. The Erdős--Hajnal conjecture---a survey. J. Graph Theory, 75(2):178–190, 2014.
* P. Erdős and A. Hajnal. Ramsey-type theorems. Discrete Appl. Math., 25(1-2):37–52, 1989.
* P. Erdős and G. Szekeres. A combinatorial problem in geometry. Compos. Math., 2:463–470, 1935.
* C. Greene. An extension of Schensted's theorem. Advances in Math., 14:254–265, 1974.
* A. Gyárfás and J. Lehel. A Helly-type problem in trees. In P. Erdős, A. Rényi, and V. T. Sos, editors, Combinatorial Theory and its Applications, II (Proc. Colloq., Balatonfüred, 1969), pages 571–584. North-Holland, Amsterdam, 1970.
* V. Jelínek and P. Valtr. Splittings and Ramsey properties of permutation classes. Adv. in Appl. Math., 63:41–67, 2015.
* T. Kaiser. Transversals of $d$-intervals. Discrete Comput. Geom., 18(2):195–203, 1997.
* G. Károlyi and G. Tardos. On point covers of multiple intervals and axis-parallel rectangles. Combinatorica, 16(2):213–222, 1996.
* J. H. Kim. On increasing subsequences of random permutations. J. Combin. Theory Ser. A, 76(1):148–155, 1996.
* B. Pittel and D. Romik. Limit shapes for random square Young tableaux.", Adv. in Appl. Math., 38(2):164–209, 2007.
* D. Romik. Permutations with short monotone subsequences. Adv. in Appl. Math., 37(4):501–510, 2006.
* R. P. Stanley. Solution to problem 5641. Amer. Math. Monthly, 76(10):1153, 1969.
* Z. G. Su. On increasing subsequences of minimal Erdős–Szekeres permutations. Acta Math. Sin. (Engl. Ser.) 27(8):1573–1580, 2011.
* G. Tardos. Transversals of $2$-intervals, a topological approach. Combinatorica, 15(1):123–134, 1995.
* The On-line Encyclopedia of Integer Sequences.
* V. Vatter. Small permutation classes. Proc. Lond. Math. Soc. (3), 103:879--921, 2011.
The layered permutation $321\ 654\ 987=\oplus^3 (321)$ and the colayered permutation $789\ 456\ 123=\ominus^3 (123)$.
We use the symbols $\oplus^k$ and $\ominus^k$ to denote repeated sums and skew sums, respectively, so the extremal Erdős–Szekeres layered permutation of length $k^2$ is
\[\oplus^k (k\cdots 21) = \underbrace{(k\cdots 21)\oplus\cdots\oplus (k\cdots 21)}_{\text{ $k$ summands}}.
\]
We show that these two families of extremal permutations are the only obstructions preventing a class from having a linear bound on monotone subsequences:
A set of $2$-intervals (left) arising from a set of axis-parallel rectangles (right).