On replica symmetry of large deviations in random graphs. Issue 1 (29th April 2014)

• Record Type: Journal Article
• Authors: Lubetzky, Eyal; Zhao, Yufei
• Is Part Of: Random structures & algorithms. Volume 47:Issue 1(2015)
• Page Start: 109
• Page End: 146
• Publication Date: 2014-04-29
• Subjects: Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20536
• Languages: English
• ISSNs: 1042-9832

Abstract

<abstract abstract-type="main"> <title>ABSTRACT</title> <p>The following question is due to Chatterjee and Varadhan (2011). Fix <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj14cqnfx7" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20536:rsa20536-math-0001" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mn>0</mml:mn><mml:mo><</mml:mo><mml:mi>p</mml:mi><mml:mo><</mml:mo><mml:mi>r</mml:mi><mml:mo><</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:math></alternatives></inline-formula> and take <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj14cqng0v" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20536:rsa20536-math-0002" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>G</mml:mi><mml:mo>∼</mml:mo><mml:mi mathvariant="script">G</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>n</mml:mi><mml:mo>, </mml:mo><mml:mi>p</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:math></alternatives></inline-formula>, the Erdős‐Rényi random graph with edge density <italic>p</italic>, conditioned to have at least as many triangles as the typical <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj14cqng2z" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20536:rsa20536-math-0003" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi mathvariant="script">G</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>n</mml:mi><mml:mo>, </mml:mo><mml:mi>r</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:math></alternatives></inline-formula>. Is <italic>G</italic> close in cut‐distance to a typical <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj14cqng3h" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20536:rsa20536-math-0004" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi mathvariant="script">G</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>n</mml:mi><mml:mo>, </mml:mo><mml:mi>r</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:math></alternatives></inline-formula> ? Via a beautiful new framework for large deviation principles in <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj14cqng65" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20536:rsa20536-math-0005" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi mathvariant="script">G</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>n</mml:mi><mml:mo>, </mml:mo><mml:mi>p</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:math></alternatives></inline-formula>, Chatterjee and Varadhan gave bounds on the replica symmetric phase, the region of <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj14cqng88" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20536:rsa20536-math-0006" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mo stretchy="false">(</mml:mo><mml:mi>p</mml:mi><mml:mo>, </mml:mo><mml:mi>r</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:math></alternatives></inline-formula> where the answer is positive. They further showed that for any small enough <italic>p</italic> there are at least two phase transitions as <italic>r</italic> 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 <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj14cqng9t" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20536:rsa20536-math-0007" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mo stretchy="false">(</mml:mo><mml:mi>p</mml:mi><mml:mo>, </mml:mo><mml:mi>r</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:math></alternatives></inline-formula> such that <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj14cqngdg" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20536:rsa20536-math-0008" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mo stretchy="false">(</mml:mo><mml:msup><mml:mi>r</mml:mi><mml:mi>d</mml:mi></mml:msup><mml:mo>, </mml:mo><mml:msub><mml:mi>h</mml:mi><mml:mi>p</mml:mi></mml:msub><mml:mo stretchy="false">(</mml:mo><mml:mi>r</mml:mi><mml:mo stretchy="false">)</mml:mo><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:math></alternatives></inline-formula> lies on the convex minorant of <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj14cqngh4" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20536:rsa20536-math-0009" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>x</mml:mi><mml:mo>↦</mml:mo><mml:msub><mml:mi>h</mml:mi><mml:mi>p</mml:mi></mml:msub><mml:mo stretchy="false">(</mml:mo><mml:msup><mml:mi>x</mml:mi><mml:mrow><mml:mn>1</mml:mn><mml:mo>/</mml:mo><mml:mi>d</mml:mi></mml:mrow></mml:msup><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:math></alternatives></inline-formula> where <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj14cqnh6p" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20536:rsa20536-math-0010" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:msub><mml:mi>h</mml:mi><mml:mi>p</mml:mi></mml:msub></mml:mrow></mml:math></alternatives></inline-formula> is the rate function of a binomial with parameter <italic>p</italic>. In particular, the answer for triangles involves <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj14cqnh31" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20536:rsa20536-math-0011" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:msub><mml:mi>h</mml:mi><mml:mi>p</mml:mi></mml:msub><mml:mo stretchy="false">(</mml:mo><mml:msqrt><mml:mi>x</mml:mi></mml:msqrt><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:math></alternatives></inline-formula> rather than the natural guess of <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj14cqnh4k" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20536:rsa20536-math-0012" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:msub><mml:mi>h</mml:mi><mml:mi>p</mml:mi></mml:msub><mml:mo stretchy="false">(</mml:mo><mml:msup><mml:mi>x</mml:mi><mml:mrow><mml:mn>1</mml:mn><mml:mo>/</mml:mo><mml:mn>3</mml:mn></mml:mrow></mml:msup><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:math></alternatives></inline-formula> where symmetry was previously known. Analogous results are obtained for linear hypergraphs as well as the setting where the largest eigenvalue of <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj14cqnhfj" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20536:rsa20536-math-0013" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>G</mml:mi><mml:mo>∼</mml:mo><mml:mi mathvariant="script">G</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>n</mml:mi><mml:mo>, </mml:mo><mml:mi>p</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:math></alternatives></inline-formula> is conditioned to exceed the typical value of the largest eigenvalue of <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj14cqnhg3" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20536:rsa20536-math-0014" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi mathvariant="script">G</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>n</mml:mi><mml:mo>, </mml:mo><mml:mi>r</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:math></alternatives></inline-formula>. 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</p> </abstract>