On replica symmetry of large deviations in random graphs

Abstract

The following question is due to Chatterjee and Varadhan (2011). Fix $0<p<r<1$ and take $G\sim G(n,p)$, the Erdős-Rényi random graph with edge density $p$, conditioned to have at least as many triangles as the typical $G(n,r)$. Is $G$ close in cut-distance to a typical $G(n,r)$? Via a beautiful new framework for large deviation principles in $G(n,p)$, Chatterjee and Varadhan gave bounds on the replica symmetric phase, the region of $(p,r)$ where the answer is positive. They further showed that for any small enough $p$ there are at least two phase transitions as $r$ varies. We settle this question by identifying the replica symmetric phase for triangles and more generally for any fixed $d$-regular graph. By analyzing the variational problem arising from the framework of Chatterjee and Varadhan we show that the replica symmetry phase consists of all $(p,r)$ such that $(r^d,h_p(r))$ lies on the convex minorant of $x\mapsto h_p(x^{1/d})$ where $h_p$ is the rate function of a binomial with parameter $p$. In particular, the answer for triangles involves $h_p(\sqrt{x})$ rather than the natural guess of $h_p(x^{1/3})$ where symmetry was previously known. Analogous results are obtained for linear hypergraphs as well as the setting where the largest eigenvalue of $G\sim G(n,p)$ is conditioned to exceed the typical value of the largest eigenvalue of $G(n,r)$. Building on the work of Chatterjee and Diaconis (2012) we obtain additional results on a class of exponential random graphs including a new range of parameters where symmetry breaking occurs. En route we give a short alternative proof of a graph homomorphism inequality due to Kahn (2001) and Galvin and Tetali (2004).

30 pages, 11 figures

References in corpus (1)

• Solution for the properties of a clustered network

Cited by in corpus (21)

• Matrix estimation by Universal Singular Value Thresholding
• An $L^p$ theory of sparse graph convergence I: limits, sparse random graph models, and power law distributions
• Upper tails and independence polynomials in random graphs
• The phases of large networks with edge and triangle constraints
• On the variational problem for upper tails in sparse random graphs
• Upper tails for arithmetic progressions in random subsets
• Independent Sets, Matchings, and Occupancy Fractions
• On the lower tail variational problem for random graphs
• Upper tails for arithmetic progressions in a random set
• The number of independent sets in an irregular graph
• Asymptotic quantization of exponential random graphs
• Upper tail bounds for Stars
• Reciprocity in directed networks
• A detailed investigation into near degenerate exponential random graphs
• Elusive extremal graphs
• Phase Transitions in Edge-Weighted Exponential Random Graphs: Near-Degeneracy and Universality
• Gradient flows on graphons: existence, convergence, continuity equations
• Algorithms for the ferromagnetic Potts model on expanders
• A large deviation principle for block models
• Ground States for Exponential Random Graphs
• On the Number of Graphs with a Given Histogram