Covering random graphs by monochromatic subgraphs, and related results

29 October 2019
Daniel Korandi

Further Information: 

How many monochromatic paths, cycles or general trees does one need to cover all vertices of a given r-edge-colored graph G? Such questions go back to the 1960's and have been studied intensively in the past 50 years. In this talk, I will discuss what we know when G is the random graph G(n,p). The problem turns out to be related to the following question of Erdős, Hajnal and Tuza: What is the largest possible cover number of an r-uniform hypergraph where any k edges have a cover of size l.

The results I mention give new bounds for these problems, and answer some questions by Bal and DeBiasio, and others. The talk is based on collaborations with Bucić, Mousset, Nenadov, Škorić and Sudakov.

  • Combinatorial Theory Seminar