5 Deducing the Bound on the Ramsey Number

Lemma 25 Lemma 5.2 in Balister et al.

Given \(n,r \in \mathbb {N}\) and \(\varepsilon {\gt} 0\), and an \(r\)-colouring of \(E(K_n)\), the following holds. There exist disjoint sets of vertices \(S_1,\dots ,S_r\) and \(W\) such that, for every \(i \in [r]\),

\[ |W| \ge \bigg( \frac{1+\varepsilon }{r} \bigg)^{\sum _{j = 1}^r |S_j|} n \qquad \text{and} \qquad |N_i(w) \cap W| \ge \bigg( \frac{1}{r} - \varepsilon \bigg) |W| - 1 \]

for every \(w \in W\), and \((S_i,W)\) is a monochromatic book in colour \(i\).

Proof ▶

We use induction on \(n\). Note that if \(n \le r\) or \(r = 1\), then the sets \(S_1 = \cdots = S_r = \emptyset \) and \(W = V(K_n)\) have the required properties. We may therefore assume that \(n {\gt} r \ge 2\), and that there exists a vertex \(x \in V(K_n)\) and a colour \(\ell \in [r]\) such that

\[ |N_\ell (x)| {\lt} \bigg( \frac{1}{r} - \varepsilon \bigg) n - 1, \]

and hence there exists a different colour \(j \ne \ell \) such that

\[ |N_j(x)| \ge \frac{1}{r-1} \bigg( n - \bigg( \frac{1}{r} - \varepsilon \bigg) n \bigg) \ge \bigg( \frac{1 + \varepsilon }{r} \bigg) n. \]

Applying the induction hypothesis to the colouring induced by the set \(N_j(x)\), we obtain sets \(S'_1,\ldots ,S'_r\) and \(W'\) satisfying the conclusion of the lemma with \(n\) replaced by \(|N_j(x)|\). Setting

\[ W = W', \qquad S_j = S'_j \cup \{ x\} \qquad \text{and} \qquad S_i = S'_i \qquad \text{for each } \, i \ne j, \]

we see that \(W\) satisfies the minimum degree condition (by the induction hypothesis), and

\[ |W| \ge \bigg( \frac{1+\varepsilon }{r} \bigg)^{\sum _{i = 1}^r |S'_i|}|N_j(x)| \ge \bigg( \frac{1+\varepsilon }{r} \bigg)^{\sum _{i=1}^r |S_i|}n. \]

Since \((S_i,W)\) is a monochromatic book in colour \(i\) for each \(i \in [r]\), it follows that \(S_1,\dots ,S_r\) and \(W\) are sets with the claimed properties.

Lemma 26 Lemma 5.3 in Balister et al.

Let \(k,r \ge 2\) and \(\varepsilon \in (0,1)\). We have

\[ R_r\big( k - s_1, \ldots , k - s_r \big) \le e^{-\varepsilon ^3 k / 2} \bigg( \frac{1+\varepsilon }{r} \bigg)^s r^{rk} \]

for every \(s_1,\ldots ,s_r \in [k]\) with \(s = s_1 + \cdots + s_r \ge \varepsilon ^2 k\).

Proof ▶

By the Erdős–Szekeres bound, we have

\[ R_r\big( k - s_1, \ldots , k - s_r \big) \le r^{rk - s}. \]

The claimed bound follows, since \(( 1 + \varepsilon )^{\varepsilon ^2 k} \ge e^{\varepsilon ^3 k/2}\) for every \(\varepsilon \in (0,1)\).

Theorem 27 Theorem 5.1 in Balister et al.

Let \(r \ge 2\), and set \(\delta = 2^{-160} r^{-12}\). Then

\begin{equation*} R_r(k) \le e^{-\delta k} r^{rk} \end{equation*}

for every \(k \in \mathbb {N}\) with \(k \ge 2^{160} r^{16}\).

Proof ▶

Given \(r \ge 2\), set \(\delta = 2^{-160} r^{-12}\), let \(k \ge 2^{160} r^{16}\) and \(n \ge e^{-\delta k} r^{rk}\), and let \(\chi \) be an arbitrary \(r\)-colouring of \(E(K_n)\). Set \(\varepsilon = 2^{-50} r^{-4}\), and let \(S_1,\ldots ,S_r\) and \(W\) be the sets given by Lemma 25. Suppose first that \(|S_1| + \cdots + |S_r| \ge \varepsilon ^2 k\), and observe that, by Lemma 26 and our lower bounds on \(n\) and \(|W|\), we have

\[ |W| \ge \bigg( \frac{1+\varepsilon }{r} \bigg)^{\sum _{j = 1}^r |S_j|} e^{-\delta k} r^{rk} \ge R_r\big( k - |S_1|, \ldots , k - |S_r| \big). \]

Since \((S_i,W)\) is a monochromatic book in colour \(i\) for each \(i \in [r]\), it follows that there exists a monochromatic copy of \(K_k\) in \(\chi \), as required.

We may therefore assume from now on that \(|S_1| + \cdots + |S_r| \le \varepsilon ^2 k\). In this case we set \(X = Y_1 = \cdots = Y_r = W\), and apply Theorem 24 to the colouring restricted to \(W\) with

\[ p = \frac{1}{r} - 2\varepsilon , \qquad \mu = 2^{30} r^3, \qquad t = 2^{-40} r^{-3} k \qquad \text{and} \qquad m = R\big( k, \ldots , k, k - t \big). \]

In order to apply Theorem 24, we need to check that \(t \ge \mu ^5/p\), and that

\[ |X| \ge \bigg( \frac{\mu ^2}{p} \bigg)^{\mu r t} \qquad \text{and} \qquad |Y_i| \ge \bigg( \frac{e^{2^{13} r^3 / \mu ^2}}{p} \bigg)^t \, m. \]

The first two of these inequalities are both easy: the first holds because \(k \ge 2^{160} r^{16}\), and for the second note that since \(n \ge r^{rk/2}\) and \(\sum _{j = 1}^r |S_j| \le rk/4\), we have

\[ |X| \ge \bigg( \frac{1+\varepsilon }{r} \bigg)^{rk/4} r^{rk/2} \ge r^{rk/4} \ge \big( 2^{61} r^7 \big)^{2^{-10} r k} \ge \bigg( \frac{\mu ^2}{p} \bigg)^{\mu r t}, \]

as required. The third inequality is more delicate: observe first that

\[ R\big( k, \ldots , k, k-t \big) \le \binom {rk-t}{k,\dots ,k,k-t} \le e^{-(r-1)t^2/3rk} r^{rk-t} \le e^{-t^2/6k} r^{rk-t}. \]

and therefore, since \(\delta \le 2^{-10} t^2/k^2\) and \(p = 1/r - 2\varepsilon \ge e^{-3\varepsilon r} / r\), we have

\[ n \ge e^{-\delta k} r^{rk} \ge r^t e^{t^2/8k} \cdot R\big( k, \ldots , k, k-t \big) \ge \frac{m}{p^t} \cdot \exp \bigg( \frac{t^2}{8k} - 3\varepsilon r t \bigg). \]

Moreover, by our choice of \(t\) and \(\mu \), we have

\[ \frac{t}{8k} = \frac{1}{2^{43} r^3} \ge \frac{1}{2^{47}r^3} + \frac{1}{2^{48}r^3} = \frac{2^{13} r^3}{\mu ^2} + 4\varepsilon r. \]

Finally, since \(\sum _{j = 1}^r |S_j| \le \varepsilon ^2 k \le \varepsilon t\), it follows that

\[ |Y_i| = |W| \ge \bigg( \frac{1+\varepsilon }{r} \bigg)^{\varepsilon t} n \ge \frac{m}{p^t} \cdot \exp \bigg( \frac{t^2}{8k} - 4\varepsilon r t \bigg) \ge \bigg( \frac{e^{2^{13} r^3 / \mu ^2}}{p} \bigg)^t \, m, \]

as claimed. Thus \(\chi \) contains a monochromatic \((t,m)\)-book, and hence, by our choice of \(m\), \(\chi \) contains a monochromatic copy of \(K_k\), as required.