UVictoria Dynamics and Probability Seminar: Joseph Hyde

  • Date: 09/19/2023
  • Time: 14:30
Joseph Hyde, University of Victoria

University of Victoria


Ramsey theory of random graphs: On the Kohayakawa-Kreuter conjecture


For graphs $G, H_1,\dots,H_r$, write $G \to (H_1, \ldots, H_r)$ to denote the property that whenever we $r$-colour the edges of $G$, there is a monochromatic copy of $H_i$ in colour $i$ for some $i \in \{1,\dots,r\}$. Mousset, Nenadov and Samotij proved an upper bound on the threshold function for the property that $G_{n,p} \to (H_1,\dots,H_r)$, thereby resolving the 1-statement of the Kohayakawa--Kreuter conjecture. We reduce the 0-statement of the Kohayakawa--Kreuter conjecture to a natural deterministic colouring problem and resolve this problem for almost all cases, which in particular includes (but is not limited to) when $H_2$ is strictly 2-balanced and either has density greater than 2 or is not bipartite. In addition, we extend our reduction to hypergraphs, proving the colouring problem in almost all cases there as well. Joint work with Candida Bowtell (University of Warwick) and Robert Hancock (Universit├Ąt Heidelberg)

Other Information: 

Time: 2:30pm Pacific

Location: DSB C130