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).
For any graph G with at least 18 nodes, either G or its complement Gc, contain complete subgraph K4 of four nodes.
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
- 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