Lesson 6

From the recurrence upper bound just proven for \(R(k,l)\), we can derive the following upper bound: \[R(k,l) \le \binom{k+l-2}{k-1}.\] Indeed, for \(k=1\) or \(l=1\), this is easily verified. For \(k,l>1\), the bound follows from the induction hypothesis: \[R(k,l) \le R(k-1,l)+R(k,l-1) \le \binom{k+l-3}{k-2}+\binom{k+l-3}{k-1}=\binom{k+l-2}{k-1}.\] The last equality is Pascal's identity: \(\binom{n-1}{k-1}+\binom{n-1}{k}=\binom{n}{k}\).

Substituting \(k=l\) into the just-proven inequality gives an upper bound on the diagonal Ramsey numbers: \[R(k,k) \le \binom{2k-2}{k-1}\le 2^{2k-2}\ .\]

It turns out that finding exact values of Ramsey numbers is a difficult task. For example, here is what is currently known about some diagonal (\(k=l\)) Ramsey numbers: \[\begin{alignat*}{3} 6 &= R(3,3) = & 6\\ 18 &= R(4,4) = & 18\\ 43 &\le R(5,5) \le & 46\\ 102 &\le R(6,6) \le & 160\\ 798 &\le R(10,10) \le & 16064\\ 17885 & \le R(19,19) \le &\ 9075135299\\\end{alignat*}\] That is, we do not know the exact value even for \(R(5,5)\)!

The recurrence relation discussed above allows us to obtain upper bounds on Ramsey numbers.

from functools import cache


@cache
def ramsey_upper(k, l):
    return 1 if min(k, l) == 1 else ramsey_upper(k - 1, l) + ramsey_upper(k, l - 1)


for n in (3, 4, 5, 6, 10, 19):
    print(n, ramsey_upper(n, n))

3 6
4 20
5 70
6 252
10 48620
19 9075135300

To prove lower bounds on Ramsey numbers, we need to present graphs that contain neither a \(k\)-clique nor an \(l\)-independent set. For example, the graphs below show that \(R(3,3) \ge 6\) and \(R(4,4) \ge 10\).

Problem. Construct an undirected graph on \(12\) vertices, in which there is neither a clique of size four nor an independent set of size four. Thus, you will prove that \(R(4,4)>12\).

As an answer, enter the edges of the graph in one line with spaces. For example, the set of edges \(\{3, 7\}, \{7, 2\}, \{2, 9\}\) should be entered as: \(\texttt{3 7 7 2 2 9}\). Assume that the vertices of the graph are the set \(\{0,1,\dotsc,11\}\).