Ramsey's Number R(5, 3)
Ramsey's Number R(5, 3) is the least integer N that solves the following problem
In any group of N people either there are 5 that know each other or there are 3 that do not know each other.
There is a symmetry in the definition: the properties of knowing and not-knowing each other can be swapped:
In any group of N people either there are 3 that know each other or there are 5 that do not know each other.
R(5, 3) = 14.
First, we show that R(5, 3) ≤ 14. This follows from the general inequality
R(m, n) ≤ R(m-1, n) + R(m, n-1),
which gives R(5, 3) ≤ R(5, 2) + R(4, 3) = 5 + 9 = 14.
Second, we exhibit a group of 13 which does not posses the required property. To this end, we shall use a bichromatic graph interpretation for the group of people where to nodes are joined by an edge iff the two persons they represent are acquainted.
In the graph below contains all the chords of lengths other than 1 and 5. There are no five nodes that form a K5, a 5-node complete graph.
The complementary graph contains no triangles:
Note: I am grateful to Stephanie Lewis for pointing out an error in an earlier version of the page and for providing the reference to J. G. Kalbfleisch' paper.
- V. K. Balakrishnan, Theory and Problems of Combinatorics, Schaum's Outline Series, McGraw-Hill, 1995, pp. 22-25
- J. G. Kalbfleisch, Construction of Special Edge-Chromatic Graphs, Canadian Math. Bull. vol. 8, no. 5, October 1965, 575-584
- 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
Copyright © 1996-2018 Alexander Bogomolny