Name
Abstract | ||
|---|---|---|
The following question is due to Chatterjee and Varadhan 2011. Fix 0<p<r<1 and take G~Gn,p, the Erd﾿s-Rényi random graph with edge density p, conditioned to have at least as many triangles as the typical Gn,r. Is G close in cut-distance to a typical Gn,r? Via a beautiful new framework for large deviation principles in Gn,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 rd,hpr lies on the convex minorant of x﾿hpx1/d where hp is the rate function of a binomial with parameter p. In particular, the answer for triangles involves hpx rather than the natural guess of hpx1/3 where symmetry was previously known. Analogous results are obtained for linear hypergraphs as well as the setting where the largest eigenvalue of G~Gn,p is conditioned to exceed the typical value of the largest eigenvalue of Gn,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. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 109-146, 2015 |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1002/rsa.20536 | Random Structures & Algorithms |
Keywords | Field | DocType |
random graphs,large deviations,replica symmetry and symmetry breaking | Discrete mathematics,Combinatorics,Random graph,Symmetry breaking,Graph homomorphism,Constraint graph,Regular polygon,Large deviations theory,Rate function,Eigenvalues and eigenvectors,Mathematics | Journal |
Volume | Issue | ISSN |
47 | 1 | Random Structures Algorithms 47 (2015) 109-146 |
Citations | PageRank | References |
5 | 0.65 | 19 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Eyal Lubetzky | 1 | 355 | 28.87 |
| Yufei Zhao | 2 | 70 | 15.60 |