3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Joffan Jan 22 '18 at 23:22
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.