5 Extremal Combinatorics 5 Extremal Combinatorics 5.2 Existence of complete subgraphs

5.1 Erdös-Szekeres lemma and Dilworth’s theorem

Let $a_{1},\ldots,a_{n}$ be a sequence of distinct numbers. A subsequence is a sequence $a_{i_{1}},\ldots,a_{i_{m}}$ where $i_{1}<i_{2}<\ldots i_{m}$ . Here $m$ is called as length of the subsequence. The subsequence is increasing (resp. decreasing) if $a_{i_{1}}<\ldots<a_{i_{m}}$ (resp. $a_{i_{1}}>\ldots>a_{i_{m}}$ ).

Theorem 5.1 (Erdös-Szekeres, 1935 ).

Let $a_{1},\ldots,a_{n}$ be a sequence of distinct numbers. If $n\geq rs+1$ then there exists an increasin subsequence of length $s+1$ or a decreasing subsequence of length $r+1$ .

The study of longest increasing subsequences touches upon combinatorics, probability, analysis, linear algebra and operator theory, differential equations, special functions, representation theory, and more; see [Romik 2015].

Proof.

(Seidenberg, 1959) Let $x_{i}$ be the length of the longest increasing subsequence ending at $a_{i}$ and $y_{i}$ be the length of the longest increasing subsequence starting at $a_{i}$ . Suppose $(x_{i},y_{i})=(x_{j},y_{j})$ for $i\neq j$ . Say $i<j$ and $a_{i}<a_{j}$ . Then the longest increasing subsequence ending at $a_{i}$ can be extended to $a_{j}$ and so $x_{j}>x_{i}$ . If $a_{i}>a_{j}$ then $y_{i}>y_{j}$ by the above reasoning. Thus $(x_{i},y_{i})\neq(x_{j},y_{j})$ for all $i\neq j$ . Consider the grid formed by $[n]\times[n]$ . Put $a_{i}$ in cell $(x_{i},y_{j})$ . By above argument, $a_{i}$ ’s fall into distinct cells and since there are $n$ many of them, at least one of them falls outside $[s]\times[r]$ . Say $a_{k}$ falls outside $[s]\times[r]$ . Then $x_{k}\geq s+1$ or $y_{k}\geq r+1$ which proves the theorem. ∎

A partial order on a set $P$ is a transitive and irreflexive binary relation $<$ i.e., $x<y$ and $y<z$ implies $x<z$ and further $x<y$ and $y<x$ cannot hold simultaneously. We say $x$ and $y$ are comparable if $x\leq y$ or $y\leq x$ . $\leq$ denotes that either $<$ or $=$ holds. A chain $C\subset P$ is a subset such that any two of its elements are comparable. A anti-chain $C\subset P$ is a subset such that no two of its elements are comparable. Observe that any chain has a greatest and smallest element.

Theorem 5.2 (Dilworth’s theorem, 1950 ).

In any partially ordered set $P$ of $n\geq sr+1$ elements there exists a chain of size $s+1$ or an anti-chain of size $r+1$ .

It will be an exercise to show that Dilowrth’s theorem implies Erdös-Szekeres lemma. We will prove a slightly stronger claim leading to Dilworth’s theorem.

Lemma 5.3 (Mirsky, 1971).

Let $P$ be a partially ordered set. If $P$ has no chain of length $m+1$ , then $P$ is a union of at most $m$ anti-chains.

Proof.

We will prove by induction. If $m=1$ , it is trivial. Let $m\geq 2$ and assume that the theorem holds for $m-1$ . Suppose $P$ has not chain of length $m+1$ elements. Let $M$ be the set of all maximal elements in $P$ . Clearly $M$ is an anti-chain. Suppose $P\setminus M$ has a chain $x_{1}<\ldots<x_{m}$ . Then this would be a maximal chain in $P$ as well and so $x_{m}\in M$ , a contradiction. Thus $P\setminus M$ has no chain of length $m$ . By induction hypothesis, $P\setminus M$ is a union of at most $m-1$ anti-chains. Thus $P$ is at most a untion of $m$ chains. ∎

Proof of Theorem 5.2.

Suppose $P$ has no chain of size $s+1$ . Then by Lemma 5.3, $P$ is a union of at most $s$ anti-chains. Since $n\geq sr+1$ , one of the anti-chains has size at least $r+1$ thereby proving the theorem. ∎

Second proof of Theorem 5.2.

We will give a second proof using pigeonhole principle directly mimicking the argument of Erdös-Szekeres lemma. Suppose $p_{i},i=1,\ldots,n$ are the elements of $P$ . Let us consider $n$ boxes. Put $p_{i}$ in box $k$ if the length of the longest chain starting at $p_{i}$ is $k$ . Suppose that $p_{i},p_{j}$ belong to the $k$ th box for some $k\in[n]$ . If $p_{i}$ and $p_{j}$ are comparable, say $p_{i}<p_{j}$ WLOG, then the longest chain starting at $p_{i}$ will be at least $k+1$ . Thus if $p_{i},p_{j}$ lie in the same box, they are not comparable. If there exists no chain of length $s+1$ , then all the $n$ elements lie in boxes $1,\ldots,s$ and so by pigeonhole principle $r+1$ elements fall in one of the boxes. Thus, these $r+1$ elements form an anti-chain by the above observation. ∎