Thresholds for random Ramsey problems (Joseph Hyde (UVic))

Graph Theory Seminar
Tuesday, February 20, 2024 - 3:30pm for 1 hour (actually 50 minutes)
Skiles 006
Joseph Hyde – University of Victoria – josephhyde@uvic.ca
Evelyne Smith-Roberge

 The study of Ramsey properties of the binomial random graph G_{n,p} was initiated in the 80s by Frankl & Rödl and Łuczak, Ruciński & Voigt. In this area we are often interested in establishing what function f(n) governs G_{n,p} having a particular Ramsey-like property P or not, i.e. when p is sufficiently larger than f(n) then G_{n,p} a.a.s. has P and when p is sufficiently smaller than f(n) then G_{n,p} a.a.s. does not have P (the former we call a 1-statement, the latter a 0-statement). I will present recent results on this topic from two different papers.

In the first, we almost completely resolve an outstanding conjecture of Kohayakawa and Kreuter on asymmetric Ramsey properties. In particular, we reduce the 0-statement to a necessary colouring problem which we solve for almost all pairs of graphs. Joint work with Candy Bowtell and Robert Hancock.

In the second, we prove similar results concerning so-called anti- and constrained-Ramsey properties. In particular, we (essentially) completely resolve the outstanding parts of the problem of determining the threshold function for the constrained-Ramsey property, and we reduce the anti-Ramsey problem to a necessary colouring problem which we prove for a specific collection of graphs. Joint work with Natalie Behague, Robert Hancock, Shoham Letzter and Natasha Morrison.