## Section 14.9 Imre Leader

Imre Bennett Leader is a British mathematician, a professor in the Department of Pure Mathematics and Mathematical Statistics at the University of Cambridge working in the field of combinatorics. He is also known as an Othello player. (See [14.9.3.1].)

Leader went on to Trinity College, Cambridge, where he graduated B.A. in 1984, M.A. in 1989, and Ph.D. in 1989, supervised by Béla Bollobás. In 1999 Leader was awarded a Junior Whitehead Prize for his contributions to combinatorics. [14.9.3.1]

### Subsection 14.9.1 Imre Leader's Favourite Proof

Professor Leader replied to our message:

Ramsey theory is packed with beautiful proofs. Almost any proof in it is elegant and lovely.

If I had to pick a favourite, perhaps it is the proof of van der Waerden: the focusing proof, where the whole idea of a product argument just comes in as an amazing thing to do — it is hard not to laugh out loud when one reads it. Even just the case of 3–term APs is good for seeing this.

Was that proof in your class? If not, let me know and I can send you some notes on it. The key thing in writeups of it is to avoid the effect of 'here is a huge bunch of symbols and so now you cannot see what is going on in the proof'! [14.9.3.2]

Since the proof of van der Waerden's theorem is already included in this project, see Section Section 14.6, we have decided to include here a proof of the Canonical Ramsey Theorem.

There were two reasons for this decision:

Dr. Daniel Král listed this theorem as his favourite, see Section Section 14.8, theorem was the favourite;

In Dr. Leader's

*Ramsey Theory*notes ([14.9.3.4]) we found a beautiful and accessible proof of the theorem.

We note that the statement of the Canonical Ramsey Theorem below is slightly different than one in Section Section 14.8.

###### Theorem 14.9.1. The Canonical Ramsey Theorem.

Whenever we have a colouring of \(\mathbb{N}^{(2)}\) with an arbitrary set of colours, there exists an infinite set \(M\) such that:

\(c\) is constant on \(\mathbb{M}^{(2)}\text{;}\) or

\(c\) is injective on \(\mathbb{M}^{(2)}\text{;}\) or

\(c(ij) = c(kl)\) iff \(i = k\) (for all \(i, j, k, \in\mathbb{M}\) with \(i\lt j\) and \(k\lt l\)); or

\(c(ij) = c(kl)\) iff \(j = l\) (for all \(i,j,k,l \in\mathbb{M}\) with \(i\lt j\) and \(k\lt l\)).

###### Proof.

First \(2\)–colour \(\mathbb{N}^{(4)}\) by giving \(ijkl\) (by which we mean henceforth \(i\lt j\lt k\lt l\)) colour YES if \(c(ij) = c(kl)\) and colour NO if \(c(ij) \neq c(kl)\text{.}\)

By Ramsey's theorem for \(4\)–sets, we have an infinite monochromatic set \(\mathbb{M}\text{.}\)

If M is coloured YES then \(\mathbb{M}\) is monochromatic for \(c\) (for given any \(ij\) and \(kl\) in \(\mathbb{M}^{(2)}\text{,}\) choose any \(m \lt n\) in \(\mathbb{M}\) with \(m\gt i, j, k, l\text{;}\) then \(c(ij) = c(mn) = c(kl)\text{.}\))

So, in this case (1) holds.

Suppose then that \(\mathbb{M}\) is coloured NO.

Now \(2\)–colour \(\mathbb{M}^{(4)}\) by giving \(ijkl\) colour YES if \(c(il) = c(jk)\) and colour NO if \(c(il) \neq c(jk)\text{.}\) Again by Ramsey's theorem, there exists an infinite \(\mathbb{M'} \in\mathbb{M}\) monochromatic for this colouring. If \(\mathbb{M'}\) is YES, choose \(x_1 \lt x_2 \lt x_3 \lt x_4 \lt x_5 \lt x_6\) in \(\mathbb{M'}\text{;}\) then \(c(x_2x_3) = c(x_1x_6) = c(x_4x_5)\text{,}\) a contradiction.

So \(\mathbb{M'}\) is colour NO.

Now \(2\)–colour \(\mathbb{M'}^{(4)}\) by giving \(ijkl\) colour YES if \(c(ik) = c(jl)\) and colour NO is \(c(ik) \neq c(jl)\text{.}\) By Ramsey's theorem, we have an infinite monochromatic set \(\mathbb{M''}\in\mathbb{M'}\text{.}\) If \(\mathbb{M''}\) is colour YES then choose \(x_1 \lt x_2 \lt x_3 \lt x_4 \lt x_5 \lt x_6\) in \(\mathbb{M''}\text{;}\) then \(c(x_1x_3) = c(x_2x_5) = c(x_4x_6)\text{,}\) a contradiction.

So \(\mathbb{M''}\) is colour NO.

Now \(2\)–colour \(\mathbb{M''}^{(3)}\) by giving \(ijk\) colour LEFTSAME if \(c(ij) = c(ik)\) and colour LEFT-DIFF if \(c(ij) \neq c(ik)\text{.}\) We get an infinite \(\mathbb{M'''}\in\mathbb{M''}\) monochromatic for this colouring. Then \(2\)–colour \(\mathbb{M'''}^{(3)}\) by giving \(ijk\) colour RIGHT-SAME if \(c(ik) = c(jk)\) and colour RIGHT-DIFF if \(c(ik)\neq c(jk)\text{.}\) We get an infinite monochromatic \(\mathbb{M''''}\in\mathbb{M'''}\text{.}\) Finally, \(2\)– colour \(\mathbb{M''''}^{(3)}\) by giving \(ijk\) colour MID-SAME if \(c(ij) = c(jk)\) and colour MID-DIFF if \(c(ij) \neq c(jk)\text{.}\) We get an infinite monochromatic \(\mathbb{M'''''}\in\mathbb{M''''}\text{.}\)

If \(\mathbb{M'''''}\) is colour MID-SAME, choose \(x_1 \lt x_2 \lt x_3 \lt x_4\) in \(\mathbb{M'''''}\text{;}\) then \(c(x_1x_2) = c(x_2x_3) = c(x_3x_4)\text{,}\) a contradiction.

So \(\mathbb{M'''''}\) is MID-DIFF.

If \(\mathbb{M'''''}\) is LEFT-SAME and RIGHT-SAME then it would also be MIDSAME, a contradiction.

If \(\mathbb{M'''''}\) is LEFT-SAME and RIGHT-DIFF then point \(3\) holds.

If \(\mathbb{M'''''}\) is LEFT-DIFF and RIGHT-SAME then point \(4\) holds.

If \(\mathbb{M'''''}\) is LEFT-DIFF and RIGHT-DIFF then point \(2\) holds.

### Subsection 14.9.2 Reflection

It is remarkable that Imre Leader and William Gasarch have chosen the same great theorem as their favourite. The proof of van der Waerden's theorem and proofs of many other Ramsey theory facts can be found in Leader's *Ramsey Theory* notes form 2000. [14.9.3.4]

### References 14.9.3 References

Imre Leader. Wikipedia. Retrieved April 7, 2024, from Wikipedia

Imre Leader. Personal Communication. February 5, 2024.

British Othello Federation, *Leader wins Nationals for 16th time*. Retrieved April 7, 2024, from BOF

Leader, I., *Ramsey Theory*, 2000. Retrieved April 7, 2024, from Notes