Ramsey Goodness of trees in random graphs.

Abstract: In 1977, Chvátal proved that every blue-red coloring of the edges of the complete graph on rn+1 vertices yields either a blue copy of the complete graph on r vertices or a red copy of each tree with r edges. This result was further extended by Burr and Erdős in 1983, starting a topic now known with the name of Ramsey goodness.

In this talk, we will discuss a random analog of Chvátal’s theorem in sparse random graphs, which is one of the first results for Ramsey numbers of large graphs in sparse random graphs. If time permits, we will discuss some details of the proof and open problems.

This is joint work with Pedro Aráujo (Prague) and Luiz Moreira (PUC Rio)

Posted on Sep 21, 2020 in Seminario de Grafos, Seminars