RAMSEY GOODNESS OF CLIQUE VERSUS PATHS IN RANDOM GRAPHS

We say that a graph G is Ramsey for H-1 versus H-2 and write G -> (H-1, H-2) if every red-blue coloring of the edges of G contains either a red copy of H-1 or a blue copy of H-2. In this paper we study the threshold for the event that the Erdos-Renyi random graph G(N, p) is Ramsey for a clique versus a path. We show that G((1 + epsilon)rn, p) -> (Kr+1, P-n) with high probability if p >> n(-2/(r+1)), and G(rn+t, p) -> (Kr+1, P-n) with high probability if p >> n(-2/(r+2)) and t >> 1/p. Both of these results are sharp (in different ways), since with high probability G(Cn, p) negated right arrow (Kr+1, P-n) for any constant C > 0 if p << n(-2/(r+1)), and G(rn+t, p) negated right arrow (Kr+1, P-n) if t << 1/p, for any 0 < p <= 1.