What is the probability that the number of triangles in an Erdős–Rényi random graph exceeds its mean by a constant factor?
The order of the log-probability was already a difficult problem until its resolution a few years ago by Chatterjee and DeMarco-Kahn. 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. I will discuss techniques for analyzing this variational problem, with the following focuses in mind:
(a) Replica symmetry: conditioned on an Erdős–Rényi random graph having lots of triangles, does it look like another Erdős–Rényi random graph with higher edge density?
(b) Computing the large deviation rate for sparse random graphs G(n,p), with p → 0 as n increases.