[Colloquium] Combinatorics & Theoretical CS Seminar

[Donna Brooms]

Combinatorics & Theoretical CS Seminar

Tuesday, May 19, 2015
Ryerson 251@ 3:00 pm
 
Yufei Zhao
M.I.T.
 
Title: “Large deviations in random graphs”
 
Abstract: What is the probability that the number of triangles in an Erdős–Rényi random graph exceeds its mean by a constant factor? In this talk, I will discuss 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 > 1/n^c for some c > 0.
 
Based on joint work with Eyal Lubetzky.
 
Host by Prof. Madhur Tulsiani
(Refreshments will be served before the talk in Ry. 255@ 2:30pm)
 
 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20150513/809d2f3f/attachment.htm