Title: Large Deviations in Random Graphs
Speaker: Yufei Zhao, MIT
Date: Monday, March 23, 2015 11:00 am
Location: CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
What is the probability that the number of triangles in an ErdH{o}s--R'enyi random graph $G(n,p)$ exceeds its mean by a constant factor? In this talk, I will survey some recent progress on this problem.
Already the order in the exponent of the tail probability was a long standing open problem until a few years ago when it was solved by DeMarco and Kahn, and independently by Chatterjee. We now wish to determine the exponential rate of the tail probability. Thanks for the works of Chatterjee--Varadhan (dense setting) and Chatterjee--Dembo (sparse setting), this large deviations problem reduces to a natural variational problem on the space of graphons. We solve this variational problem asymptotically, thereby determining the large deviation rate, which is valid at least for $p geq n^{-alpha}$ for some $alpha > 0$.
Based on joint work with Eyal Lubetzky.
See: http://math.rutgers.edu/seminars/allseminars.php?sem_name=Discrete%20Math