On replica symmetry of large deviations in random graphs. Issue 1 (29th April 2014) - Lubetzky, Eyal; Zhao, Yufei
ABSTRACT The following question is due to Chatterjee and Varadhan (2011). Fix <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj14cqnfx7" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />0<p<r<1</alternatives> and take <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj14cqng0v" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />G∼G(n, p)</alternatives>, the Erdős‐Rényi random graph with edge density p, conditioned to have at least as many triangles as the typical <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj14cqng2z" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />G(n, r)</alternatives>. Is G close in cut‐distance to a typical <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj14cqng3h" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />G(n, r)</alternatives> ? Via a beautiful new framework for large deviation principles in <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj14cqng65" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />G(n, p)</alternatives>, Chatterjee and Varadhan gave bounds on the replica symmetric phase, the region of <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj14cqng88" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />(p, r)</alternatives> 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 <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj14cqng9t" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />(p, r)</alternatives> such that <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj14cqngdg" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />(rd, hp(r))</alternatives> lies on the convex minorant of <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj14cqngh4" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />x↦hp(x1/d)</alternatives> where <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj14cqnh6p" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />hp</alternatives> is the rate function of a binomial with parameter p. In particular, the answer for triangles involves <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj14cqnh31" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />hp(x)</alternatives> rather than the natural guess of <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj14cqnh4k" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />hp(x1/3)</alternatives> where symmetry was previously known. Analogous results are obtained for linear hypergraphs as well as the setting where the largest eigenvalue of <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj14cqnhfj" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />G∼G(n, p)</alternatives> is conditioned to exceed the typical value of the largest eigenvalue of <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj14cqnhg3" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />G(n, r)</alternatives>. 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