4.1: The Pigeon Hole Principle

A function \(f:X \rightarrow Y\) is said to be 1–1 (read one-to-one) when \(f(x) \neq f(x′)\) for all \(x,x′ \in X\) with \(x \neq x′\). A 1–1 function is also called an injection or we say that \(f\) is injective. When \(f:X \rightarrow Y\) is 1–1, we note that \(|X| \leq |Y|\). Conversely, we have the following self-evident statement, which is popularly called the “Pigeon Hole” principle.

Proposition 4.1. Pigeon Hole Principle

If \(f: X \rightarrow Y\) is a function and \(|X|>|Y|\), then there exists an element \(y \in Y\) and distinct elements \(x,x′ \in X\) so that \(f(x) = f(x') = y\).

In more casual language, if you must put \(n+1\) pigeons into \(n\) holes, then you must put two pigeons into the same hole.

Here is a classic result, whose proof follows immediately from the Pigeon Hole Principle.

Theorem 4.2. Erdós/Szekeres Theorem

If \(m\) and \(n\) are non-negative integers, then any sequence of \(mn+1\) distinct real numbers either has an increasing subsequence of \(m+1\) terms, or it has a decreasing subsequence of \(n+1\) terms.

Proof

Let \(\sigma = (x_1,x_2,x_3,...,x_{mn+1})\) be a sequence of \(mn+1\) distinct real numbers. For each \(i=1,2,…,mn+1\), let \(a_i\) be the maximum number of terms in a increasing subsequence of \(\sigma\) with \(x_i\) the first term. Also, let \(b_i\) be the maximum number of terms in a decreasing subsequence of \(\sigma\) with \(x_i\) the last term. If there is some \(i\) for which \(a_i \geq m+1\), then \(\sigma\) has an increasing subsequence of \(m+1\) terms. Conversely, if for some \(i\), we have \(b_i \geq n+1\), then we conclude that \(\sigma\) has a decreasing subsequence of \(n+1\) terms.

It remains to consider the case where \(a_i \leq m\) and \(b_i \leq n\) for all \(i=1,2,…,mn+1\). Since there are \(mn\) ordered pairs of the form \((a,b)\) where \(1 \leq a \leq m\) and \(1 \leq b \leq n\), we conclude from the Pigeon Hole principle that there must be integers \(i_1\) and \(i_2\) with \(1 \leq i_1 < i_2 \leq mn+1\) for which \((a_{i1},b_{i1})=(a_{i2},b_{i2})\). Since \(x_{i1}\) and \(x_{i2}\) are distinct, we either have \(x_{i1}< x_{i2} \) or \(x_{i1}>x_{i2}\). In the first case, any increasing subsequence with \(x_{i2}\) as its first term can be extended by prepending \(x_{i1}\) at the start. This shows that \(a_{i1}>a_{i2}\). In the second case, any decreasing sequence of with \(x_{i1}\) as its last element can be extended by adding \(x_{i2}\) at the very end. This shows \(b_{i2} > b_{i1}\).

In Chapter 11, we will explore some powerful generalizations of the Pigeon Hole Principle. All these results have the flavor of the general assertion that total disarray is impossible.