Seminars & Colloquia Calendar

Download as iCal file

Special Colloquium

From Janson's inequality to hypergraph containers

Rajko Nenadov, Google Zurich

Location:  Zoom
Date & time: Friday, 03 December 2021 at 11:30AM - 12:30PM

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.

This talk is for the local Rutgers Math Community only. Zoom links will be sent by the Department Chair via email

Special Note to All Travelers

Directions: map and driving directions. If you need information on public transportation, you may want to check the New Jersey Transit page.

Unfortunately, cancellations do occur from time to time. Feel free to call our department: 848-445-6969 before embarking on your journey. Thank you.