Chapter 3: Pigeonhole Principle

This is a reading note of Introductory Combinatorics by Richard A. Brualdi.

The following aspects are ones that are most important within this chapter:

• Simple Version of Pigeonhole Principle
• Application of Simple Pigeonhole Principle
• Enhanced Version of Pigeonhole Principle
• Applications of Enhanced Pigeonhole Principle
• Ramsey Theorem

Simple Version of Pigeonhole Principle

Statement: If we have $n + 1$ objects and put them into $n$ boxes, then there exists one box with at least 2 objects within it.

Proof: Assume every box can satisfy the condition that there is no box with more than one object, then there are at most $n$ objects. However, we start with $n + 1$ objects, contradiction. Therefore, there exists one box with at least 2 objects.

Application of Simple Pigeonhole Principle

Applications: There are many of them, but one of the most interesting application given in the book is to use the simple version of pigeonhole principle to prove Chinese Reminder Theorem.

Chinese Reminder Theorem:

If we have two relatively-prime integers $n,m$ and two integers $a,b$ ($0\leq a \leq n,0\leq b \leq m$). Then, there exists an integer $x$ which can be written in forms of $x = pn + a$ and $x = qm + b$.

Lets consider $n$ integer numbers, where each can be written in form of $im + a, 0 \leq i \leq n – 1$. Assume there are two numbers that has same reminders mod $n$. So we have $i_{1}m + a = q_1n + b$ and $i_2m + a = q_2n + b$. If we substract two equations, then we have $(i_1 – i_2)m = (q_1 – q_2)n$. Since $m$ and $n$ are relatively prime, $n$ can only be a factor of $(i_1 – i_2)$. However, $\forall i, 0\leq i \leq n – 1 \rightarrow \max(i_1 – i_2) \leq n – 1$. So, $n$ cannot be a factor of $(i_1 – i_2)$ either, contradiction. So, no two numbers have same reminders when mod $n$. Because we consider a set of $n$ numbers, there must be $n$ reminders when mod $n$. So, according to Pigeonhole Principle, every reminder from 0 to $n – 1$ has to exist, including $b$. Therefore, the theory is proved.

Enhanced Version of Pigeonhole Principle

Statement: Assume we have $(\sum_{i = 1}^{n}q_i) – n + 1$ objects and $q_i$ is an integer. If we put these objects into $n$ boxes, there are either $q_1$ objects in the first box, or either $q_2$ objects in the second box, …, or either $q_n$ objects in the $n$-th box.

Proof: This can be proved similarly as the simple version. Assume we satisfy the condition that none of the boxes will be like the status in the statement, then we have the total number of objects distributed in the boxes as $\sum_{i = 1}^{n}(q_i – 1) = (\sum_{i = 1}^{n}q_i) – n$. Appearntly, we have one more object to put, therefore proved the statement.

Note: It is interesting to notice that the simple version of pigeonhole principle is a special condition when $q_1 = q_2 = q_3 = \cdots = q_n = 2$ and $\sum_{i = 1}^{n}(q_i) – n + 1 = 2n – n + 1 = n + 1$.

Application of Enhanced Pigeonhole Principle

Among the examples of applications introduced in the book, the discoveries by P. Erdos and A. Szekeres is the one that I think most interesting.

Statement: For every real number seqeunce with length $n^2 + 1$, it either contains an increasing subsequence of length $n + 1$ or a decreasing subsequence of length $n + 1$.

Definiton of Subsequence: Assume $a_1,a_2,\cdots,a_n$ is a sequence. Then, a subsequence would be $a_{i_1},a_{i_2},\cdots,a_{i_k}, 1 \leq k \leq n$ and $\forall j < k,i_j < i_k$.

Proof: Assume there is no increasing subsequence with length $ n + 1$ and let $count(i)$ be the length of increasing subsequence starting of $a_i$. Since there is no increasing subsequence with length $n + 1$, $\forall i,count(i) \leq n$. Because there are $n^2 + 1$ counts, if we consider these as objects and $n$ different possible values of $count$ as boxes, then we have $n^2 + 1 =(\sum_{i = 1}^{n}q_ i) – n + 1$, so $n(n + 1) = \sum_{i = 1}^{n}q_i$. So there exist one box (possible value for $count$) that has $n + 1$ objects. If we have some $i_j < i_k$ in this box that $a_{i_j} < a_{i_k} $, then we can build a longer increasing subsequence by putting $a_{i_j}$ in front of the increasing subsequence starting from $i_k$. Therefore, we will have $m_{i_k} > m_{i_j}$, contradict to the status that they are in the same box (have same $count$ value). Therefore, for all of the $n + 1$ objects in the box, we have that $a_{i_1} \geq a_{i_2} \geq \cdots \geq a_{i_{n + 1}}$, which forms a decreasing subsequnce of length $n + 1$. The existence of increasing subsequnce can be proven similarly.

Ramsey Theorem

A simple and easy version of this theorem included in the book is that in every 6 people, either there are three people know each other or there exist three people don’t know each other. Now, lets use a more formal way to describe this theorem.

Definition of Complete Graph: A complete graph is a graph with $n$ nodes and $\frac{n(n – 1)}{2}$ edges that connect every pairs of node $(u,v)$ where $u \not= v$. We use symbol $K_n$ to denote a complete graph with $n$ nodes. Here are some complete graphs.
(http://https://appledorem.com/wp-content/uploads/2018/07/JxZGM.png)

Then, the simple version of ramsey theorem can be expressed as $K_6 \rightarrow K_3,K_3$. It means that if we have a complete graph with six nodes and the edges are colored with red and blue, then either we will have a triangle with only red edges or a triangle with only blue edges.

Rasmey Theorem: For every given integers $m$ and $n$ that $m,n\geq2$, we know that $\exist p \in \mathbb{Z^+},K_p \rightarrow K_m,K_n$.

Proof: To be added….

Rasmey Number: $r(m,n)$ is the smallest $p$ that satisfies the condition that $K_p \rightarrow K_m,K_n$.

It is easy to see that $r(2,n) = r(n,2) = n$ , we call these numbers as naive Rasmey number when $n \geq 2$.

Rasmey Number call also be extended in to cases with more colors, and we have a more generalized version of Rasmey theorem and Rasmey number.

Generalized Rasmey Theorem: Assume a color set $C$, which $|C| \geq 2$, and let $c_i$ be its components. Assume $n$ integers $q_1,q_2,\cdots,q_n \geq |C|$. Then, $\exist p \in \mathbb{Z^+},K_p^{|C|} \rightarrow K_{q_1}^{|C|},K_{q_2}^{|C|},\cdots,K_{q_n}^{|C|}$.

Generalized Rasmey Number: $r_{|C|}(q_1,q_2,\cdots,q_n)$ be the smallets $p$ that satisfies the condition that $K_p^{|C|} \rightarrow K_{q_1}^{|C|},K_{q_2}^{|C|},\cdots,K_{q_n}^{|C|}$ and $r_3(3,3,3) = 17$ is the only smallest integer $p$ that is known so far as non-trivial Rasmey number.

Relationship with Pigeonhole Principle: What if $|C| = 1$? Then, $r_1(q_1,q_2,\cdots,q_n)$ represents the minimum $p$ that to either have $q_1$ objects with color $c_1$, or $q_2$ objects with color $c_2$, …, or $q_n$ objects with color $c_n$. Therefore, according to the pigeonhole principle, we know that $r_1(q_1,q_2,\cdots,q_n) = (\sum_{i = 1}^{n}q_i) – n + 1$.

​