Ramsey goodness of trees in random graphs

Abstract

For graphs G, H and a family of graphs., we write G ->(H,P) to denote that every blue-red coloring of the edges of G contains either a blue copy of H, or a red copy of each F is an element of P For integers n and D, let tau(n, D) denote the family of all trees with n edges and maximum degree atmostD. We prove that for each r, D >= 2, there exist constants C, C' > 0 such that if p >= Cn(-2/(r+2)) and N >= rn + C'/p, then G(N, p)->(Kr+ 1, tau(n, D)) with high probability. This is a random version of a well-known result of Chvatal from 1977. 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.os-Sos conjecture for trees with linear size and bounded maximum degree, which may be of independent interest.