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).

Proposition

For any graph G with at least 18 nodes, either G or its complement G^c, contain complete subgraph K₄ of four nodes.

Proof

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 |S| ≥ 9 or |T| ≥ 9.

If |T| ≥ 9, then either there is in T K₄ or three mutually disjoint nodes. In the former case, we immediately have a K₄. In the latter case, adjoining A to the three disjoint nodes, shows the existence of K₄ in G^c.

If |S| ≥ 9, we use the fact that R(4, 3) = R(3, 4) to claim that either there is in S K₃ or four mutually disjoint nodes. In the latter case, we immediately have a K₄ in G^c. In the former case, adjoining A to K₃ in S shows the existence of K₄ in G.

Theorem

R(4, 4) = 18.

Proof

For a proof we only need to exhibit a 17-node graph G such that neither G nor G^c contain K₄.

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.

References

1. V. K. Balakrishnan, Theory and Problems of Combinatorics, Schaum's Outline Series, McGraw-Hill, 1995, pp. 22-25
2. T. Gowers (ed.), The Princeton Companion to Mathematics, Princeton University Press, 2008, p. 562
3. J. G. Kalbfleisch, Construction of Special Edge-Chromatic Graphs, Canadian Math. Bull. vol. 8, no. 5, October 1965, 575-584

Resource Limit Is Reached

The website is temporarily unable to service your request as it exceeded resource limit. Please try again later.

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

Copyright © 1996-2018 Alexander Bogomolny