You are here

When is the probability of avoiding a graph super-exponentially small?

Rajko Nenadov, Google Zürich
Wednesday, November 17, 2021 - 3:30pm to 5:00pm
PDL C-38 and via Zoom Link:
Rajko Nenadov
Rajko Nenadov


Start with \$K_n\$, a complete graph with \$n\$ vertices, and choose \$m\$ edges uniformly at random. This basic model of random graphs is known as the the Erdős–Rényi \$G(n,m)\$ model. One of the fundamental questions is how does the probability that \$G(n,m)\$ does not contain some chosen graph \$H\$ change as \$m\$ goes from \$1\$ to \$\binom{n}{2}?\$ When \$H\$ is bipartite, at some point this probability becomes exponentially small in \$m\$ and soon after super-exponentially small. However, when \$H\$ is not bipartite it remains exponential almost all the way to the end. Slightly rephrased, the celebrated KŁR conjecture states that in order to go to super-exponentially small probabilities it suffices to condition on uniform edge distribution, the archetypal property of random graphs.

The KŁR conjecture owes its fame to applications: It implies that with high probability all subgraphs of the binomial random graph with appropriate parameters satisfy an embedding lemma which complements the sparse regularity lemma, from which a large number of results in random graph theory follow. The conjecture was proven in 2015 by Balogh, Morris, and Samotij and, independently, Saxton and Thomason, using the newly developed hypergraph containers method. In this talk we will discuss a new, direct proof of this conjecture.

Note: This talk begins with a pre-seminar (aimed at graduate students) at 3:30–4:00. The main talk starts at 4:10.

Join Zoom Meeting:
Meeting ID: 915 4733 5974