Probability Seminar

Upper tails and independence polynomials in sparse random graphs
Monday, January 11, 2016 - 4:30pm to 5:30pm
Sequoia Hall, Room 200
Bhaswar Bhattacharya (Stanford)
Abstract / Description: 

The upper tail problem in the Erd˝os–R´enyi random graph G ∼ Gn,p is to estimate the probability that the number of copies of a graph H in G exceeds its expectation by a factor 1 + δ. Already, for the case of triangles, the order in the exponent of the tail probability was a long-standing open problem until fairly recently, when it was solved by Chatterjee (2012), and independently by DeMarco and Kahn (2012). Recently, Chatterjee and Dembo (2014) showed that in the sparse regime, the logarithm of the tail probability reduces to a natural variational problem on the space of weighted graphs. In this talk we derive the exact asymptotics of the tail probability by solving this variational problem for any fixed graph H. As it turns out, the leading order constant in the large deviation rate function is governed by the independence polynomial of H.

This is based on joint work with Shirshendu Ganguly, Eyal Lubetzky, and Yufei Zhao.


The Probability Seminars are held in Sequoia Hall, Room 200, at 4:30pm on Mondays. Refreshments are served at 4pm in the Lounge on the first floor.