Ramsey goodness of trees in random graphs

Abstract

For a graph $G$, we write $G\to (K_{r+1},\mathcal{T}(n,D))$ if every blue-red colouring of the edges of $G$ contains either a blue copy of $K_{r+1}$, or a red copy of each tree with $n$ edges and maximum degree at most $D$. In 1977, Chvátal proved that for any integers $r,n,D\ge 2$, $K_N\to (K_{r+1},\mathcal{T}(n,D))$ if and only if $N\ge rn+1$. We prove a random analogue of Chvátal's theorem for bounded degree trees, that is, we show that for each $r,D\ge 2$ there exist constants $C,C^{\prime }>0$ such that if $p\ge C{n}^{-2/(r+2)}$ and $N\ge rn+C^{\prime }/p$, then \[G(N,p) \rightarrow \big(K_{r+1},\mathcal{T}(n,D)\big)\] with high probability as $n\to \infty$. The proof combines a stability argument with the embedding of trees in expander graphs. Furthermore, the proof of the stability result is based on a sparse random analogue of the Erdős--Sós conjecture for trees with linear size and bounded maximum degree, which may be of independent interest.

30 pages, 3 figures