On the size of $(K_{t_1},\dots ,K_{t_k})$-co-critical graphs

Abstract

Given integers $k\ge 2$ and $t_1,\dots ,t_k\ge 2$, we write \emph{$G\to (K_{t_1},\dots ,K_{t_k})$} if every $k$-coloring of the edges of a graph $G$ contains a monochromatic copy of $K_{t_i}$ in color $i$ for some $i\in \{1,\dots ,k\}$. A non-complete graph $G$ is \emph{$(K_{t_1},\dots ,K_{t_k})$-co-critical} if $G\nrightarrow (K_{t_1},\dots ,K_{t_k})$, but $G+e\to (K_{t_1},\dots ,K_{t_k})$ for every edge $e\notin E(G)$. Let $r=R(K_{t_1},\dots ,K_{t_k})$ denote the Ramsey number. In 1987, Hanson and Toft conjectured that every $(K_{t_1},\dots ,K_{t_k})$-co-critical graph $G$ on $n\ge r$ vertices satisfies \[|E(G)|\ge (r-2)n- \binom{r- 1}{2}.\] This bound is best possible for every $n\ge r$. More recently, the present author conjectured that every such graph has minimum degree at least $r-2$. Using the $q$-neighbor bootstrap percolation closure method, here we prove that the Hanson-Toft Conjecture holds asymptotically, provided that the minimum-degree conjecture is true; more precisely, If every $(K_{t_1},\dots ,K_{t_k})$-co-critical graph has minimum degree at least $r-2$, then there is a constant $C=C(r,k)$ such that every $(K_{t_1},\dots ,K_{t_k})$-co-critical graph $G$ on $n\ge r$ vertices satisfies $|E(G)|\ge (r-2)n-C$.