APR Seminar: Bhaswar B. Bhattacharya (University of Pennsylvania)

April 20, 2017 | 1:10pm - 2:10pm

APR Seminar: Bhaswar B. Bhattacharya (University of Pennsylvania)

Mudd Hall 303
Title: Upper Tails and Independence Polynomials in Sparse Random Graphs
 
Abstract: The upper tail problem in the Erdos-Renyi random graph [G\sim\mathcal{G}_{n,p}] is to estimate the probability that the number of copies of a graph [H] in [G] exceeds its expectation by a  factor [1+\delta] . 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.)
 
Bio: Bhaswar B. Bhattacharya is an Assistant Professor in the Department of Statistics at the Wharton School, University of Pennsylvania. He received his Ph.D. from the Department of Statistics at Stanford University in 2016. Prior to that, he obtained his Bachelor and Master degrees in Statistics from the Indian Statistical Institute, Kolkata in 2009 and 2011, respectively. His research interests include discrete probability, non-parametric statistics, and discrete geometry.


500 W. 120th St., Mudd 315, New York, NY 10027    212-854-2942                 
©2014 Columbia University