Ramsey's Number R(4, 4)
Noga Alon and Michael Krivelevich [The Princeton Companion to Mathematics, p. 562] present a story of the Ramsey number R(4, 4),
In the course of an examination of friendship between children some fifty years ago, the Hungarian sociologist Sandor Szalai observed that among any group of about twenty children he checked he could always find four children any two of whom were friends, or else four children no two of whom were friends. Despite the temptation to try to draw sociological conclusions, Szalai realized that this might well be a mathematical phenomenon rather than sociological one. Indeed, a brief discussion with the mathematicians Erdös, Turán, and Sós convinced him this was the case.
The phenomenon Szalai has observed falls into the purview of Ramsey's theory, while 20 is a rough estimate to the Ramsey number R(4, 4).
Pick a node, say, A. The nodes of G are split into two groups: those that are joined to A (group S) and those that are not (group T). Either
R(4, 4) = 18.
For a proof we only need to exhibit a 17-node graph G such that neither G nor Gc contain K4.
Place 17 nodes on a circle and join all the chords of lengths 1, 2, 4, and 8.
The complementary graph consists of chords of lengths 3, 5, 7, and 11.
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
- T. Gowers (ed.), The Princeton Companion to Mathematics, Princeton University Press, 2008, p. 562
- J. G. Kalbfleisch, Construction of Special Edge-Chromatic Graphs, Canadian Math. Bull. vol. 8, no. 5, October 1965, 575-584
Copyright © 1996-2018 Alexander Bogomolny