# 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_{4} 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

If _{4} or three mutually disjoint nodes. In the former case, we immediately have a K_{4}. In the latter case, adjoining A to the three disjoint nodes, shows the existence of K_{4} in G^{c}.

If _{3} or four mutually disjoint nodes. In the latter case, we immediately have a K_{4} in G^{c}. In the former case, adjoining A to K_{3} in S shows the existence of K_{4} 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_{4}.

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

- 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

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

Copyright © 1996-2018 Alexander Bogomolny