6 Deducing the Bound on the Ramsey Number

In this section we will deduce Theorem 1, the bound on the Ramsey numbers \(R_r(k)\), from Theorem 35. We will in fact prove a stronger quantitative version of the theorem in the form of Theorem 38.

In order to apply Theorem 35, we need to find a suitable collection of sets \(X,Y_1,\ldots ,Y_r\) in an arbitrary \(r\)-colouring of \(E(K_n)\). To do so, we simply run the Erdős–Szekeres process until we find a subset of the vertex set in which each colour has density close to \(1/r\), and the colouring is close to regular in each colour.

Lemma 36 Single Erdős-Szekeres step

Lemma 5.2

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]\),

\begin{equation*} |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 \end{equation*}

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

\begin{equation*} |N_\ell (x)| {\lt} \bigg( \frac{1}{r} - \varepsilon \bigg) n - 1, \end{equation*}

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

\begin{equation*} |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. \end{equation*}

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

\begin{equation*} W = W’, \qquad S_j = S’_j \cup \{ x\} \qquad \text{and} \qquad S_i = S’_i \qquad \text{for each } \, i \ne j, \end{equation*}

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

\begin{equation*} |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. \end{equation*}

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.

The next lemma, which is an immediate consequence of the Erdős–Szekeres bound on the \(r\)-colour Ramsey numbers, implies (roughly speaking) that either the sets \(S_1,\dots ,S_r\) given by Theorem 36 satisfy \(|S_i| = o(k)\) for each \(i \in [r]\), or we are already done.

Lemma 37 Many Erdős-Szekeres steps bound

Lemma 5.3

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

\begin{equation*} 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} \end{equation*}

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

\begin{equation*} R_r\big( k - s_1, \ldots , k - s_r \big) \le r^{rk - s}. \end{equation*}

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

Theorem 38 Quantitative main theorem

Theorem 5.1

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 Theorem 36. Suppose first that \(|S_1| + \cdots + |S_r| \ge \varepsilon ^2 k\), and observe that, by Theorem 37 and our lower bounds on \(n\) and \(|W|\), we have

\begin{equation*} |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). \end{equation*}

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 35 to the colouring restricted to \(W\) with

\begin{equation*} 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). \end{equation*}

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

\begin{equation*} |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. \end{equation*}

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

\begin{equation*} |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}, \end{equation*}

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

\begin{equation*} 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}. \end{equation*}

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

\begin{equation*} 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). \end{equation*}

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

\begin{equation*} \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. \end{equation*}

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

\begin{equation*} |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, \end{equation*}

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.