Ramsey's Number R(3, 3, 3)
In general, the Ramsey number R(p1, p2, ..., pn; k), where k and p1, p2, ..., pn are positive integers, is the least such N that a complete graph KN colored into k colors, has a monochromatic subgraph Kps for at least on
According to [Gardner, p. 443] it was first proved in 1955 that
Below, we shall first prove that R(p1, p2, ..., pn) exists and then proceed to establish the value for R(3).
Suppose p1, p2, ..., pn are positive integers. Then there exists an integer
From R(m, n) ≤ R(m-1, n) + R(m, n-1) it follows that the theorem holds for
What we actually proved could be expressed as
R(p1, p2, ..., pn) ≤ R(p1, R(p2, ..., pn)).
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:
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.
Denote the topics discussed by the students T1, T2, T3. Consider one of the students, say A. Since A 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, T1. Then there are just to possibilities. If any pair from the 6 students discussed topic T1 we are done. Otherwise, there are 6 students that discussed between themselves only 2 topics - T2 or T3. So we are looking at the number
To prove that indeed R(3) = 17 requires to exhibit a coloring of K16 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.
- 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
Copyright © 1996-2018 Alexander Bogomolny