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.

Proposition

R(5, 3) = 14.

Proof

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 K₅, a 5-node complete graph.

Ramsey number R(5, 3)

The complementary graph contains no triangles:

Ramsey number R(5, 3) - a complementary graph

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
J. G. Kalbfleisch, Construction of Special Edge-Chromatic Graphs, Canadian Math. Bull. vol. 8, no. 5, October 1965, 575-584

72389924