Chapter 24 \(R(4,4) = 18\text{:}\) Before Your Eyes
Project by: Max Liu and Sloan Wensauer.
\(\textbf{Summary:}\) “\(R(4,4) = 18\text{:}\) A Proof Without Words” is a video proof of \(R(4, 4) = 18\text{.}\) It is an animation made with Manim, a Python library for creating mathematical animations, and the final video was edited with Quicktime. The background music “Ramsey's Nocturne” was an original piece by Brian Kong (Math 301, 2014) and played by Max Liu in the video.
The proof consists of two parts, both involving the colouring of edges in a graph.
The first part shows that finding a monochromatic \(K_4\) in a two–coloured \(K_{18}\) is unavoidable, proving that \(R(4, 4) \leq 18\text{.}\) The beginning of the video utilizes the theorem \(R(s,t) \leq R(s-1, t) + R(s, t-1)\text{,}\) saying that \(R(4,4) \leq R(3,4) + R(4, 3)\text{.}\) It is established that \(R(3,4) = R(4,3) = 9\) by exhausting different colourings of \(K_9\) to show that a monochromatic \(K_3\) or a monochromatic \(K_4\) is unavoidable. Every colouring of the edges from one vertex is shown, and the Pigeonhole Principle is put on display by showing that no matter how you proceed with colouring the remaining edges, you either end up with a monochromatic \(K_3\) subgraph or a monochromatic \(K_4\) subgraph. The theorem is then used to show that \(R(4,4) \leq R(3,4) + R(4,3) = 9 + 9 = 18\text{.}\) From this we have that \(R(4,4) \leq 18\text{.}\)
The second part shows that getting a monochromatic \(K_4\) in a two–coloured \(K_{17}\) is avoidable, proving that \(R(4,4) \gt 17\text{.}\) This is done by showing a colouring of a \(K_{17}\) that has no monochromatic \(K_4\) anywhere. In the video, the red and blue edges of \(K_{17}\) split into two edge–disjoint subgraphs to give the viewers a better look at the red and blue colourings. By taking random selections of four vertices at a time, it is shown that there is no \(K_4\) in the red or blue subgraph. Merging the colours together shows the \(K_{17}\) once again with the knowledge that there is no monochromatic \(K_4\) anywhere. The existence of a two–colouring of \(K_{17}\) that avoids a monochromatic \(K_4\) proves that \(R(4,4) \not= 17\text{,}\) implying \(R(4,4) \gt 17\text{.}\) Combining \(R(4, 4) \leq18\) from part 1 and \(R(4,4) \gt 17\) from part 2 gives us \(R(4,4) = 18\text{,}\) proving the Ramsey number.
Overall, this project greatly solidified our knowledge of Ramsey's Theorem and encouraged us to approach the problem creatively. By not only visualizing, but creating the visualization ourselves, we now thoroughly understand the methodical way of colouring graphs and using the Pigeonhole Principle to prove that certain coloured complete graphs cannot avoid monochromatic complete subgraphs. We also gained a better understanding of proofs by case and proofs by contradiction. This project required us to combine our computer science and math skills to create a unique, memorable end product. We had a lot of fun problem–solving and finding the best way to visually represent the proof. This project has inspired us to consider other mathematical proofs that can be represented in video form.
Watch a video with the proof below.