Lesson 8

Below, we present an elegant proof of the lower bound on \(R(k,k)\).

Theorem (Erdős, 1947). For \(k \ge 3\), it holds that \[R(k,k) > 2^{\frac{k-1}{2}}\ .\] That is, there exists a graph with \(2^{\frac{k-1}{2}}\) vertices having neither a clique of size \(k\) nor an independent set of size \(k\).

Proof. Let \(n=2^{\frac{k-1}{2}}\). Consider the uniform distribution on all \(2^{\binom{n}{2}}\) undirected graphs on \(n\) vertices. We will show that a random graph has the required property with positive probability. To do this, we will prove that the probability of the complement of this event (i.e., that the graph does not have the required property) is less than one.

Let \(G(V,E)\) be a random graph and \(A \subseteq V\) be a subset of its vertices of size \(k\). Let \(X_{A}\) denote the event "the vertices of set \(A\) form a clique or an independent set in \(G\)". Then \[\Pr[X_{A}]= 2 \cdot \frac{2^{\binom{n}{2}-\binom{k}{2}}}{2^{\binom{n}{2}}}=2^{-\binom{k}{2}+1}\ .\] Now, let \(p\) denote the probability that \(G\) contains a clique or an independent set of size \(k\). Then \[\begin{align*}p&=\Pr\left[\bigcup_{A \subseteq V \colon |A|=k}X_{A}\right] \le&\text{(union bound)}\\&\le \sum_{A \subseteq V \colon |A|=k}\Pr[X_{A}]=\\&=\binom{n}{k}\cdot 2^{-\binom{k}{2}+1}\le&\text{(\(k \ge 3\))}\\&\le \frac{n^k}{2\cdot 3}\cdot 2^{-\binom{k}{2}+1}=&\text{(\(n=2^{\frac{k-1}{2}}\))}\\&= \frac{2^{k(k-1)/2}}{2\cdot 3}\cdot 2^{-\binom{k}{2}+1}=\\&=\frac{1}{3}\ .\end{align*}\] Thus, with probability at least \(2/3\), \(G\) contains neither a clique nor an independent set of size \(k\).◼