Ramsey's Theorem: Friends and Strangers

Section 2.2 Ramsey's Theorem: Friends and Strangers

A friend to all is a friend to none. — Aristotle, Greek philosopher, 384 BCE - 322 BCE

Example 2.2.1.

Edge 2-Colouring. Use TWO colours, red and blue, for example, to colour the edges of \(K_6\text{,}\) a complete graph on six vertices. See Figure 2.2.2. Each edge should be coloured by only one colour.

Figure 2.2.2. \(K_6\) - a complete graph on six vertices

Two Questions:

How many different edge 2-colourings of \(K_6\) are there?
Can you find a monochromatic triangle in your colouring, i.e., three edges coloured by the same colour that form a triangle?

BIG Question: Does any edge 2-colouring of \(K_6\) yield a monochromatic triangle?

BIG Answer: Yes, any edge 2-colouring of \(K_6\) yields a monochromatic triangle!

Theorem 2.2.3.

Ramsey's Theorem - Special Case. Any edge 2-colouring of \(K_6\) yields a monochromatic \(K_3\text{.}\)

Proof.

Recall the pigeonhole principle: suppose you have \(k\) pigeonholes and \(n\) pigeons to be placed in them. If \(n > k\) then at least one pigeonhole contains at least two pigeons. See Figures 2.2.4 and Figures 2.2.5.

Figure 2.2.4. Proof: Step 1 and Step 2

Figure 2.2.5. Proof: Step 3 — Two cases

Question. Is this true for any edge 2-colouring of \(K_5\text{?}\) See Figure 2.2.6.

Figure 2.2.6. Find an edge 2-colouring of \(K_5\) that avoids monochromatic triangles

A Dinner Party Problem. Suppose that six people are gathered at a dinner party. Then there is a group of three people at the party who are either all mutual acquaintances or all mutual strangers. See Figure 2.2.7.

Figure 2.2.7. Do we know each other? \(\color{blue}{\text{YES}}\) or \(\color{red}{\text{NO}}\) .

Claim 2.2.8.

Any edge 2-colouring (blue and red) of \(K_{10}\) yields a red \(K_4\) or a blue \(K_3\text{.}\)

Proof.

See Figures 2.2.9 and Figure 2.2.10.

Figure 2.2.9. Fix one vertex: \(\color{blue}{\blacksquare}\text{.}\) There are at least 6 red adjacent edges OR at least 4 blue adjacent edges.

Figure 2.2.10. Two cases

Claim 2.2.11.

Any edge 2-colouring (blue and red) of \(K_{9}\) yields a red \(K_4\) or a blue \(K_3\text{.}\)

Proof.

See Figures 2.2.12 and Figure 2.2.13

Figure 2.2.12. Step 1: If there is a vertex \(\color{blue}{\blacksquare}\) with at least 6 red adjacent edges OR at least 4 blue adjacent edges - DONE

Figure 2.2.13. Step 2 — EVERY vertex \(\color{blue}{\blacksquare}\) is adjacent with 5 red edges AND with 3 blue edges

The number of the blue edges altogether is:

\begin{equation*} \frac{\text{ (# of vertices) } \cdot \text{ (# of incident blue edges) } }{2}=\frac{9\cdot 3}{2}=13.5 \end{equation*}

Something went wrong!

Question. Does every blue-red edge colouring of \(K_8\) yield a red \(K_4\) or a blue \(K_3\text{?}\) See Figure 2.2.14.

Figure 2.2.14. Find a blue-red edge colouring of \(K_8\) with neither red \(K_4\) nor blue \(K_3\)

Theorem 2.2.15.

Ramsey's Theorem - Special Case. Any blue-red edge colouring of \(K_{9}\) yields a red \(K_4\) or a blue \(K_3\text{.}\)

Theorem 2.2.16.

Ramsey's Theorem - Special Case. \(R(4,3)=R(3,4)=9\text{.}\)

Theorem 2.2.17.

Ramsey's Theorem - Special Case. \(R(4,4)\leq 18\text{.}\)

Proof.

Consider a blue-red edge colouring of a \(K_{18}\text{.}\) See Figures 2.2.18 and Figure 2.2.19

Figure 2.2.18. Step 1: Observe that each vertex \(\color{blue}{\blacksquare}\) is adjacent to at least 9 edges of the same colour - say red

Figure 2.2.19. Step 2 — Two cases

Theorem 2.2.20.

Actually... \(R(4,4)=18\)

Resources.