Lesson 2

In the 1950s, a Hungarian sociologist noticed that among any twenty children, there are always either four who all know each other or four who do not know each other at all. He consulted mathematicians Erdős, Turan, and Sos, who explained that this is not a coincidence, but a mathematical fact and a special case of the general Ramsey theory. Roughly speaking, this theory states that complete disorder is impossible: in any arbitrarily complex structure with a sufficiently large number of elements, there will always be a substructure satisfying some property.

For numbers \(k,l \in \mathbb{Z}_{\ge 1}\), the Ramsey number \(R(k,l)\) is defined as the smallest number \(n\) such that in any graph with \(n\) vertices, there exists either a clique of size \(k\) or an independent set of size \(l\).

For example, it is known that among any six people, there exist either three who are mutually acquainted or three who are mutually unacquainted. At the same time, it may also happen that there are both three mutually acquainted and three mutually unacquainted individuals. For example, in the second graph below, there is a \(3\)-clique \(\{1, 2, 5\}\) and a \(3\)-independent set \(\{1, 3, 4\}\).

Let us prove that \(R(3,3)=6\).

To do this, consider six people and fix one of them—say, Alice. Suppose that out of the remaining five people, Alice knows \(a\) people and does not know \(b\) people. Then \(a+b=5\), and one of these numbers must be at least three. Let this number be \(a\). (The case \(b \ge 3\) is analyzed similarly.) If among these \(a\) people there are two who know each other, then we have found a clique of size three: this is Alice and these two acquaintances. However, if none of these \(a\) people know each other, then they form an independent set of size \(a \ge 3\).

Problem. Is this proof correct?