Skip to main content

Chapter 23 \(R(3,3,3) = 17\text{:}\) Before Your Eyes

Project by: Haruto Matsui, Anthony Vendrasco, and Kaj Wilson.

\(\textbf{Summary:}\) Our project goal is to demonstrate that \(R(3,3,3)=17\) in a proof without words.

To check this by brute force, we would need \(3^{16\choose 2}=3^{120}\approx 1.8\cdot 10^{57}\) possibilities, which is way too large to check by hand or by computer.

A more efficient method that we use to prove this fact, is by starting from the basics.

This is to say, we introduce the pigeonhole principle, then consider what a complete graph is, followed by building an understanding of Ramsey numbers. Next, we propose a method of determining how to solve \(R(s,t)\) for small enough \(s,t,\in \mathbb{N}\text{.}\) Lastly, we will use this method to determine \(R(3,3)=6\) and consequently \(R(3,3,3)=17\text{.}\)

We use the following:

  1. The pigeonhole principle states that if we want to put \(n\) pigeons into \(k\) pigeonholes, and \(n\gt k\text{,}\) there must be at least one pigeonhole with \(\lceil \frac{n}{k}\rceil\) pigeons.

  2. A complete graph is a graph where any two vertices are connected by an edge. Further, the conventional notation is \(K_s\) with \(n\in\mathbb{N}\) denoting the number of vertices so that \(K_n\) has \({n\choose 2}\) edges.

  3. The Ramsey number \(R(s,t)=M\) denotes the minimum number of vertices of the complete graph \(K_N\) such that an edge \(2\)– colouring yields a monochromatic \(K_s\) or a monochromatic \(K_t\text{.}\)

Lastly, our main method of proving \(R(3,3)=6\) and \(R(3,3,3)=17\) starts by fixing a vertex of the complete graph in question. Then, we apply an edge colouring of all of the edges from our fixed vertex and apply the pigeonhole principle to determine how many of them are of one colour or another.

From this colouring, we isolate the edges of a single colour to reduce our problem. Then, we consider cases of the edge colouring on the remaining edges of our reduced problem.

Finally, we conclude that such a monochromatic \(K_3\) will exist in the complete graphs in question by the case analysis.