The Ramsey number of books

Ramsey’s Theorem is among the most well-known results in combinatorics. The theorem states that any two-edge-coloring of a sufficiently large complete graph contains a large monochromatic complete subgraph. Indeed, any two-edge-coloring of a complete graph with $N=4^{t-o(t)}$ vertices contains a monochromatic copy of $K_t$. On the other hand, a probabilistic argument yields that there exists a two-edge-coloring of a complete graph with $N=2^{t/2+o(t)}$ with no monochromatic copy of $K_t$. Much attention has been paid to improving these classical bounds but only improvements to lower order terms have been obtained so far.

A natural question in this setting is to ask whether every two-edge-coloring of a sufficiently large complete graph contains a monochromatic copy of $K_t$ that can be extended in many ways to a monochromatic copy of $K_{t+1}$. Specifically, Erdős, Faudree, Rousseau and Schelp in the 1970’s asked whether every two-edge-coloring of $K_N$ contains a monochromatic copy of $K_t$ that can be extended in at least $(1-o_k(1))2^{-t} N$ ways to a monochromatic copy of $K_{t+1}$. A random two-edge-coloring of $K_N$ witnesses that this would be best possible. While the intuition coming from random constructions can be misleading, for example, a famous construction by Thomason shows the existence of a two-edge-coloring of a complete graph with fewer monochromatic copies of $K_t$ than a random two-edge-coloring, this paper confirms that the intuition coming from a random construction is correct in this case. In particular, the author answers this question of Erdős et al. in the affirmative. The question can be phrased in the language of Ramsey theory as a problem on determining the Ramsey number of book graphs. A book graph $B_t^{(k)}$ is a graph obtained from $K_t$ by adding $k$ new vertices and joining each new vertex to all the vertices of $K_t$. The main result of the paper asserts that every two-edge-coloring of a complete graph with $N=2^kt+o_k(t)$ vertices contains a monochromatic copy of $B_t^{(k)}$.