# Ramsey's Number R(3, 3, 3)

In general, the *Ramsey number* R(p_{1}, p_{2}, ..., p_{n}; k), where k and p_{1}, p_{2}, ..., p_{n} are positive integers, is the least such N that a complete graph K_{N} colored into k colors, has a monochromatic subgraph K_{ps} for at least on _{1}, p_{2}, ..., p_{n}); and when all p's are equal, the notation is further shortened to R(p), or R_{p}. Thus, say, R(3) stands for

According to [Gardner, p. 443] it was first proved in 1955 that

Below, we shall first prove that R(p_{1}, p_{2}, ..., p_{n}) exists and then proceed to establish the value for R(3).

### Ramsey's Theorem

Suppose p_{1}, p_{2}, ..., p_{n} are positive integers. Then there exists an integer _{1}, p_{2}, ..., p_{n})_{1}, p_{2}, ..., p_{n}),_{v} with n colors will contain a subgraph K_{ps} with all edges of color s, for at least on s.

### Proof

See [Allenby & Slomson, Theorem 16.10; Wallis & George, 3.3].

From R(m, n) ≤ R(m-1, n) + R(m, n-1) it follows that the theorem holds for _{0} = R(p_{2}, ..., p_{n})_{0}, p_{1})_{v} in colors _{p0} in color 0 or K_{p1} in color 1. In the latter case we are done. In the former, return the just found K_{p0} to the original colors. By the inductive hypothesis K_{p0} contains a monochromatic graph K_{ps} for some s from

What we actually proved could be expressed as

R(p_{1}, p_{2}, ..., p_{n}) ≤ R(p_{1}, R(p_{2}, ..., p_{n})).

So, in particular, R(3) = R(3, 3, 3) ≤ R(3, R(3, 3)) = R(3, 6) = 18. A problem offered at the 1964 International Mathematical Olympiad claims that R(3) ≤ 17:

### Theorem

Each of 17 students talked with every other student. They all talked about three different topics. Each pair of students talked about one topic. Prove that there are three students that talked about the same topic among themselves.

### Proof

Denote the topics discussed by the students T_{1}, T_{2}, T_{3}. Consider one of the students, say * A*. Since

*talked about three topics to 16 other students, by the Pigeonhole Principle, there are at least 6 students with whom*

**A***talked of a single topic, say, T*

**A**_{1}. Then there are just to possibilities. If any pair from the 6 students discussed topic T

_{1}we are done. Otherwise, there are 6 students that discussed between themselves only 2 topics - T

_{2}or T

_{3}. So we are looking at the number

To prove that indeed R(3) = 17 requires to exhibit a coloring of K_{16} in three colors with no monochromatic triangle. Such a graph exists and is formed by three overlapping copies of the Clebsch graph, each of which is colored in one of the three given colors.

## Reference

- R. B. J. T. Allenby, A. Slomson,
*How to Count: An Introduction to Combinatorics*, CRC Press, 2011 (2nd edition) - D. Djukić et al,
*The IMO Compendium*, Springer, 2011 (Second edition) - M. Gardner,
*The Colossal Book of Mathematics*, W. W. Norton & Co, 2001 - W. D. Wallis, J. C. George,
*Introduction to Combinatorics*, Chapman and Hall/CRC, 2010, p. 52

|Contact| |Front page| |Contents| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny