Ramsey numbers of cycles in random graphs

Pedro Araújo

Czech academy of sciences

October 6, 2022, 12:20 in S6


Let G,H be graphs. We write G -> H to say that every blue/red-coloring of the edges of G contains a copy of H whose edges all have the same colour. The study of such property is called Ramsey Theory and it is one of the most fruitful fields of research in Combinatorics.

In general, it is very hard to determine if G -> H, but there are some classes of graphs that make the problem more approachable. Here we consider one example in this class, where H is a cycle on n vertices, denoted by C_n. We call the minimum N such that K_N-> H by R(H), the Ramsey number of H. It is known that R(C_n) = 2n-1 if n is odd and R(C_n) = 3n/2 - 1 if n is even.

Here we transfer this property of the complete graph to random graphs. We consider G=G(N,p) to be a graph on N vertices where each pair belongs to G with probability p=p(N) and we investigate for which functions p(n) we have the property G -> C_n. We show that there exist C>0 such that if p > C/N then with high probability we have G(N,p) -> C_n if N > R(C_n)+C/p. Moreover, the bounds on p and on N are best possible, up to the constant.

This is joint work with Matías Pavez-Signé and Nicolás Sanhueza-Matamala.