## Section 14.2 Steve Butler

Steve Butler is an American mathematician with a focus on graph theory, combinatorics, the mathematics of juggling, and calculus. Butler has taught many math courses at the University of Iowa. One of Butler's most significant publications is *Egyptian fractions with each denominator having three distinct prime divisors* which he published with Paul Erdős and Ron Graham. This means that Butler has an Erdős number of one. Butler also has a YouTube channel with a focus on mathematics. [14.2.3.1]

### Subsection 14.2.1 Butler's favourite proof

According to Butler's email, the legendary mathematician Ron Graham told a story about when he was working on the book *Ramsey Theory* with Joel Spencer (also in this document) and Bruce Rothschild. All three assumed that everything was proofread and that the proof for Ramsey's theorem was correct. However, this was not the case and the proof for Ramsey's theorem in the first edition of their *Ramsey Theory* book was incorrect.

Butler's favourite proof is the use of induction and the pigeonhole principle to prove existence in Ramsey theory. In Dr. Butler's words:

In response to your question I am simple at heart and like the idea that what appears complicated follows readily from basic ideas. By this I mean to say that I like the combination of induction and pigeon-hole that can be used to prove existence in Ramsey Theory (yes, absolutely terrible bounds, but what is several thousand orders of magnitude among friends). [14.2.3.2]

This proof was chosen by our group to demonstrate Butler's preferences.

###### Theorem 14.2.1.

\(R(s, t) \leq R(s-1, t) + R(s, t - 1)\text{.}\)

###### Proof.

Base case: \(s, t = 3,\ s + t = 6\text{.}\) Since \(R(2, 2) = 2,\ R(3, 2) = R(2, 3) = 3,\ R(2, 4) = R(4, 2) = 4,\ R(3, 3) = 6\text{.}\) This means that when \(s + t = 4,\ 5,\ 6\) there must exist a Ramsey number.

Inductive hypothesis: assume \(n \geq 6\) and for any \(u, v \geq 3\) such that \(u + v = n\text{,}\) the Ramsey number \(R(u, v)\) exists.

Inductive step: let \(s, t, \geq 3\) such that \(s + t = n + 1\text{.}\) Since \((s - 1) + t = s + (t - 1) = n\text{.}\) By assumption, both \(R(s - 1, t)\) and \(R(s, t - 1)\) exists. Let \(M = R(s - 1, t) + R(s, t - 1)\text{.}\) Now consider a two–colouring (red and blue) of the complete graph \(K_M\text{.}\)

Each vertex in this graph will have degree \(M - 1 = R(s - 1, t) + R(s, t - 1) - 1\text{.}\) Now focus on one vertex, and count the number of edges that are red and the number of edges that are blue.

By the pigeonhole principle, there are at least \(R(s - 1, t)\) red edges or at least \(R(s, t - 1)\) blue edges.

Assume there are at least \(R(s - 1, t)\) red edges.

Now consider the subgraph of \(K_M\text{,}\) \(K_{R(s - 1, t)}\text{.}\) By definition, there must be a red \(K_{s - 1}\) or a blue \(K_t\text{.}\) If \(K_{R(s - 1, t)}\) contains a red \(K_{s - 1}\text{,}\) we have a red \(K_s\) since the initial vertex's incident edges were all red as well.

In the other case, there is a blue \(K_t\) in \(K_{R(s - 1, t)}\text{,}\) which implies that \(K_M\) also has a blue \(K_t\text{.}\)

This proves that any two–colouring of the edges contains a red \(K_s\) or a blue \(K_t\text{.}\)

By the principle of mathematical induction, there exists a \(R(s, t)\text{,}\) which is bounded by \(R(s - 1, t) + R(s, t - 1)\text{.}\) [14.2.3.3]

### Subsection 14.2.2 Reflection

It is fascinating that a relatively simple proving technique can be used to establish many deep and complicated Ramey theory facts.

### References 14.2.3 References

Steve Butler. (n.d.). SteveButler.org. Retrieved April 12, 2024, from www.mathbutler.org

Steve Butler. Personal Communication. February 12, 2024.

Jungić, V. (2023). *Basics of Ramsey theory.*Chapman and Hall.