Skip to main content
Logo image

Applied Combinatorics

Section 11.5 Ramsey’s Theorem

By this time, you are probably not surprised to see that there is a very general form of Ramsey’s theorem. We have a bounded number of bins or colors and we are placing the subsets of a fixed size into these categories. The conclusion is that there is a large set which is treated uniformly.
Here’s the formal statement.
We don’t include the proof of this general statement here, but the more ambitious students may attempt it on their own. Note that the case \(s=1\) is just the Pigeon Hole Principle, while the case \(s=r=2\) is just Ramsey’s Theorem for Graphs. An argument using double induction is required for the proof in the general case. The first induction is on \(r\) and the second is on \(s\text{.}\)