# Question on proof of Erdos and Szekeres

So my textbook has a specific proof of the theorem by Erdos and Szekeres

We suppose that there is no increasing subsequence of length $n + 1$ and show that there must be a decreasing subsequence of length $n + 1$. For each $k = 1,2, ... ,n^2 + 1$ let $m_k$ be the length of the longest increasing subsequence that begins with $a_k$. Suppose $m_k\leq n$ for each $k = 1,2, ... ,n^2 + 1$, so that there is no increasing subsequence of length $n + 1$. Since $m_k \geq 1$ for each $k = 1,2, ... ,n^2 + 1$, the numbers $m_1, m_2, ... , m_{n^2+1}$ are $n^2 + 1$ integers each between 1 and $n$. By the strong form of the pigeonhole principle, $n + 1$ of the numbers $m_l, m_2, . .. , m_{n^2+1}$ are equal. Let $m_{k_{1}} = m_{k_{2}} = ... = m_{k_{n+1}}$, where $1\leq k_1<k_2<...<k_{n+1}\leq n^2+1$

My question is how can the strong pigeonhole principle be used to say that $n+1$ increasing subsequences are equal. According to the pigeonhole principle if we have positive integers $q_1, q_2, ..., q_p$ and we distribute $q_1+q_2+...+q_p-p+1$ objects then either the 1st box has at least $q_1$ objects, or 2nd box has has at least $q_2$, etc. So do the lengths of the sequences $m_1, m_2,..., m_{n+1}$ match up to the $q_1, q_2, ..., q_p$ integers.

I have trouble seeing what the objects are and what the boxes are. I thought initially that the objects would be the sequences, but I have trouble figuring out what the boxes are in that scenario.

• The strong form of the pigeonhole principle is easiest for me to understand stated as: If $ab{+}1$ objects are distributed into $b$ boxes, then some box has at least $a{+}1$ objects. – Joffan Jan 22 '18 at 23:22

The boxes are the numbers $1,2,\ldots,n$.
The objects are the indices $1,2,\ldots,n^2+1$.
The index $k$ is placed in the box $j$ if and only if $m_k=j$.
The number of objects is more than $n$ times the number of boxes, so there is a box containing more than $n$ objects. That is, a box containing $n+1$ objects (at least).
Say $k_1,k_2,\ldots,k_{n+1}$ are all in the same box. By definition this means that $m_{k_1},m_{k_2},\ldots,m_{k_{n+1}}$ are all equal.