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 1 ≤ s ≤ k. Where n = k, k is usually omitted: R(p1, p2, ..., pn); and when all p's are equal, the notation is further shortened to R(p), or Rp. Thus, say, R(3) stands for R(3, 3, 3) which in turn is the same as R(3, 3, 3; 3).

According to [Gardner, p. 443] it was first proved in 1955 that R(3) = 17; but already in 1964 the problem has been offered at the International Mathematical Olympiad.

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 R(p1, p2, ..., pn) such that if v ≥ R(p1, p2, ..., pn), then any coloring of the edges of Kv with n colors will contain a subgraph Kps 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 n = 2. To apply mathematical induction, assume that it holds for n = t-1. Then p0 = R(p2, ..., pn) exists. Select v ≥ R(p0, p1) and color Kv in colors 1, 2, ..., t. Then replace colors 2, 3, ..., t with a new color 0. Either there is Kp0 in color 0 or Kp1 in color 1. In the latter case we are done. In the former, return the just found Kp0 to the original colors. By the inductive hypothesis Kp0 contains a monochromatic graph Kps for some s from 2 ≤ s ≤ t.

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 R(3, 3) which is 6; and we are done in this case also.

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.

240px-Clebsch_Lombard.png 220px-Clebsch_graph.png

Reference

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

  1. Ramsey's Theorem
  2. Party Acquaintances
  3. Ramsey Number R(3, 3, 3)
  4. Ramsey Number R(4, 3)
  5. Ramsey Number R(5, 3)
  6. Ramsey Number R(4, 4)
  7. Geometric Application of Ramsey's Theory
  8. Coloring Points in the Plane and Elsewhere
  9. Two Colors - Two Points
  10. Three Colors - Two Points
  11. Two Colors - All Distances
  12. Two Colors on a Straight Line
  13. Two Colors - Three Points
  14. Three Colors - Bichromatic Lines
  15. Chromatic Number of the Plane
  16. Monochromatic Rectangle in a 2-coloring of the Plane
  17. Two Colors - Three Points on Circle
  18. Coloring a Graph
  19. No Equilateral Triangles, Please

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

Copyright © 1996-2017 Alexander Bogomolny

 62637012

Search by google: