Seminar

Zoom Link

A foundational result of Luczak-Rucinski-Voigt and Frankl-Rodl is that there are constants C > c > 0 such that if p > C n^{-1/2}, then every two-coloring of the edges of G=G_{n,p} produces a monochromatic triangle (in which case we say G is Ramsey for triangles), while if p < c n^{-1/2}, then there is a two-coloring avoiding monochromatic triangles. Moreover, Freidgut-Rodl-Rucinski-Tetali showed that this Ramsey property has a sharp threshold: there is a function c'(n) such that G is Ramsey for triangles above c'(n) n^{-1/2} and not Ramsey below. The existence of a sharp threshold suggests that there may be a phase transition in G responsible for the appearance of the Ramsey property, but the relevant phenomena remain mysterious; even showing that c'(n) is in fact a constant remains wide open. We show that c'(n) is between (approximately) \sqrt{2.75} and 4.95. We also establish that (the same) \sqrt{2.75} n^{-1/2} is a sharp "threshold" for the appearance of two-dimensional homology in the clique-complex of the random graph, and we give a conjecturally sharp lower bound for the two-dimensional collapsibility threshold of G (around \sqrt{2.45}, as predicted by Newman). These topological statements are two-dimensional analogues of the emergence of the giant component in the ordinary random graph. Underlying all results is an understanding of the density of cores in random hypergraphs which in turn relies on an impressive application (by Kanazawa, building on Linial-Peled) of the theory of local weak convergence. Joint with Tom Bohman and Bob Krueger.

Random Ramsey, homology, and high-dimensional phase transitions in random graphs