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).
Ramsey's Theorem
Suppose p1, p2, ..., pn are positive integers. Then there exists an integer
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
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:
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 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.
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

- Ramsey's Theorem
- Party Acquaintances
- Ramsey Number R(3, 3, 3)
- Ramsey Number R(4, 3)
- Ramsey Number R(5, 3)
- Ramsey Number R(4, 4)
- Geometric Application of Ramsey's Theory
- Coloring Points in the Plane and Elsewhere
- Two Colors - Two Points
- Three Colors - Two Points
- Two Colors - All Distances
- Two Colors on a Straight Line
- Two Colors - Three Points
- Three Colors - Bichromatic Lines
- Chromatic Number of the Plane
- Monochromatic Rectangle in a 2-coloring of the Plane
- Two Colors - Three Points on Circle
- Coloring a Graph
- No Equilateral Triangles, Please

|Contact| |Front page| |Contents| |Algebra|
Copyright © 1996-2018 Alexander Bogomolny
72255455