A reminder: this is today.
On 2 October 2022 20:05:48 CEST, Mykhaylo Tyomkyn tyomkyn@kam.mff.cuni.cz wrote:
Dear all,
It is a new semester, and we are resuming the noon seminar series. Our first speaker on Thursday 6 October will be Pedro Araújo. Please find the talk details below.
Best regards, Misha Tyomkyn.
Ramsey numbers of cycles in random graphs Pedro Araújo Czech academy of sciences October 6, 2022, 12:20 in S6
Abstract 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.
TCS-l mailing list -- tcs-l@kam.mff.cuni.cz To unsubscribe send an email to tcs-l-leave@kam.mff.cuni.cz