Seminars & Colloquia Calendar

Abstract:Start with a complete graph with n vertices, and choose m edges uniformly at random. This basic model of random graphs is known as 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 ex(H, n), the largest number of edges in an H-free graph. A standard approach to this question is via Janson's inequality. Surprisingly, and in contrast to the binomial random graph model G(n,p), this approach does not always correctly determine the order of the logarithm of the probability when H is a bipartite graph. In particular, a recent result of Balogh, Morris, and Samotij shows that in this case the probability eventually becomes super-exponentially small in m, whereas Janson's inequality reaches a plateau at an exponential bound.

In the first part of the talk we discuss a new proof of this result and its connection to the celebrated K?R conjecture. In the second part we discuss applications of these results in Ramsey theory and the motivation for revisiting the problem. Finally, generalising the presented ideas, we give a strengthening of Janson's inequality in the spirit of the so-called hypergraph containers, one of the most influential results in probabilistic combinatorics in the last decade.