PaperlayerView exact revision on arXiv

Source-linked AI summary

On replica symmetry of large deviations in random graphs

Eyal Lubetzky, Yufei Zhao

arXiv:1210.7013v2math.PRmath.CO

TL;DR

The paper asks when a graph conditioned on an excess of triangles resembles a typical denser Erdős–Rényi graph. It analyzes graphon variational problems to identify the replica-symmetric phase for triangles and regular subgraphs, finding a triangle boundary governed by h_p(√x) rather than the natural cube-root curve.

  • Problem

    For G(n,p) conditioned to have at least as many triangles as a typical G(n,r), the question is whether it becomes close in cut-distance to G(n,r), rather than forming a special structure.

    Source: §1 · p. 1

  • Method

    The authors analyze the graphon variational problems arising from the Chatterjee–Varadhan framework for large deviations.

    Source: §1.1 · p. 4

  • Results

    For triangle upper tails, the replica-symmetric phase is governed by h_p(√x), not h_p(x^(1/3)), and the analysis identifies the phase for fixed d-regular subgraphs.

    Source: §1 · p. 1, §1.1 · p. 2

  • Takeaways & Limitations

    The triangle result settles the cut-distance question in a larger replica-symmetric region than the previously known cube-root criterion.

    Source: §1.1 · p. 2

    The hypergraph extension is restricted to fixed linear hypergraphs; for general H, the corresponding counting lemma is unavailable in the described framework.

    Source: §5 · p. 21

Abstract

from arXiv · show

The following question is due to Chatterjee and Varadhan (2011). Fix $0<p<r<1$ and take $G\sim G(n,p)$, the Erd\H{o}s-R\'enyi 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).

1. Introduction

The paper resolves when triangle-rich G(n,p) graphs resemble typical G(n,r) graphs and extends the phase-diagram analysis to regular subgraphs and other random-graph settings. It also studies a generalized exponential random graph model and gives a new proof of a graph homomorphism inequality.

1. Introduction

  • The paper addresses whether conditioning G(n,p) on an unusually high triangle count makes it close in cut-distance to a typical G(n,r), a behavior that depends on p and r.The competing explanations are uniformly distributed excess edges or fewer edges arranged in a special structure.Source: §1 · p. 1

1.1. Subgraph densities and spectral radii.

  • For triangles, the cube-root curve x↦h_p(x^(1/3)), reflecting the three edges, is only a natural candidate; the replica-symmetric phase is strictly larger and is governed instead by x↦h_p(√x).Source: §1.1 · p. 2
  • The largest-eigenvalue upper-tail problem has the same phase boundary as triangle counts, and both results follow from analyzing Chatterjee–Varadhan graphon variational problems.Within the replica-symmetric region the variational solution is uniquely symmetric; outside it, graphons can outperform that candidate.Source: §1.1 · p. 4

1.2. Exponential random graphs.

  • In the generalized exponential random graph model, symmetry breaking occurs for some positive-β2 parameters when α < 2/3, whereas replica symmetry always holds when α ≥ 2/3.The result applies to any fixed d-regular graph H.Source: §1.2 · p. 5, Figure 3 · p. 5

1.3. Linear hypergraphs.

  • The paper extends the large-deviation analysis to densities of fixed linear d-regular hypergraphs in random hypergraphs.Linearity supports a suitable extension of the regularity lemma; the stated extension does not cover arbitrary hypergraphs.Source: §1.3 · p. 6

1.4. Graph homomorphisms.

  • The authors give a short entropy-free proof of the Galvin–Tetali graph homomorphism inequality, following Kahn.Their proof follows as an immediate consequence of a generalized form of Hölder’s inequality.Source: §1.4 · p. 6

1.5. Organization.

  • The paper reviews graph limits and large deviations, proves the subgraph and spectral results, then treats exponential random graphs, linear hypergraphs, homomorphism inequalities, and open problems.Source: §1.5 · p. 7

2. Graph limits and the framework of Chatterjee-Varadhan

Graphons represent dense graphs and make cut-distance a compact framework for studying graph limits. The Chatterjee–Varadhan large-deviation principle reduces conditioning questions to a variational problem whose minimizers describe the conditioned graph’s limiting structure.

2.1. Graph limits.

  • Dense graph sequences converge through their subgraph densities, and graphons provide limit objects for every such convergent sequence.The cut-distance topology is equivalent to convergence of all fixed subgraph densities.Source: §2.1 · pp. 7–8
  • The cut-distance quotient of graphons is compact, and subgraph densities are continuous in this topology.These properties make cut-distance a natural setting for graph limits and large-deviation analysis.Source: §2.1 · p. 8

2.2. Graph parameters in the cut-metric topology.

  • A nice graph parameter is cut-distance continuous and has no local extrema that are not global; subgraph density qualifies, while Frobenius norm and max-cut do not.The Frobenius norm is discontinuous in cut-distance, and max-cut fails the local-extrema condition.Source: §2.2 · pp. 8–9

2.3. Large deviations for random graphs.

  • For nice graph parameters, the large-deviation rate is a graphon entropy minimization, and a unique minimizer determines the conditioned graph’s limiting structure.When the minimizer is unique, the conditional distribution converges to its point mass.Source: §2.3 · p. 10

3. The phase diagram for subgraph densities and the spectral radius

For upper-tail subgraph densities and largest-eigenvalue deviations, replica symmetry is determined by whether the constant graphon minimizes the associated entropy variational problem. When it does not, constructions with lower entropy give symmetry breaking; for certain bipartite graphs and for spectral lower tails, replica symmetry holds throughout.

3.1. Subgraph density.

  • The generalized Hölder inequality strengthens standard Hölder under a bound on how many functions involve each coordinate, supporting the symmetric-phase argument.The stated bound is that each coordinate appears in at most d of the sets A_i.Source: §3.1 · pp. 10–11
  • For a fixed d-regular H, the upper-tail symmetric solution is characterized by (r^d, hp(r)) lying on the convex minorant of x -> hp(x^(1/d)); otherwise a lower-entropy competitor exists.The criterion follows by comparing the constant graphon with the variational problem’s minimizers.Source: §3.1 · pp. 11–13
  • For bipartite H satisfying Sidorenko’s conjecture, every lower-tail deviation is replica symmetric.The result applies to fixed graphs for which the conjecture holds.Source: §3.1 · p. 13

3.2. Largest eigenvalue.

  • For upper tails of the largest eigenvalue, the symmetric solution is governed by whether (r^2, hp(r)) lies on the convex minorant of x -> hp(sqrt(x)); outside it, a lower-entropy graphon beats the constant one.The graphon operator norm extends the normalized largest eigenvalue λ1(G)/n.Source: §3.2 · pp. 14–16
  • Lower-tail deviations of the largest eigenvalue are replica symmetric throughout, with no phase transition.The proof reduces the constraint to an upper bound on the graphon’s L1 norm.Source: §3.2 · p. 16

4. Exponential random graph models

The section analyzes exponential random graph models through a variational problem, identifying when its maximizers are constant and when symmetry breaks. The geometry of a transformed rate-function curve explains discontinuities in the symmetric solution and helps locate symmetry-breaking regimes.

4. Exponential random graph models

  • The large-n analysis reduces the exponential random graph model to a graphon variational problem, and generalized Hölder’s inequality supports the constant-function solution in the symmetric regime.When replica symmetry holds, the model behaves like an Erdős–Rényi graph with edge density u*, or a mixture when there are two distinct constant maximizers.Source: §4 · pp. 16, 17, 20
  • When α ≥ d/e(H), the model has replica symmetry; outside a parameter curve Γ there is one constant maximizer, while inside Γ there are exactly two.The theorem also gives replica symmetry for 0 < α < d/e(H) when β1 ≥ log(d − 1) − d/(d − 1).Source: §4 · p. 17
  • For 0 < α < d/e(H) and β1 < log(d − 1) − d/(d − 1), an open interval of β2 values yields broken symmetry.In this interval, no constant function maximizes the variational problem.Source: §4 · p. 17
  • When the transformed rate-function curve is nonconvex, the symmetric optimizer u* jumps between two values at one critical slope; otherwise it varies continuously.The two-point jump occurs when a lower tangent touches the curve at both points.Source: §4 · p. 18
  • When 0 < e(H)α ≤ 1 or e(H)α > 1 with p ≥ p0(e(H)α), optimization problem (4.3) has a unique maximizing u; otherwise, only one β2 value has two distinct maximizing u’s.Source: §4 · p. 19
  • In the (p, u) phase diagram, u* rises with β2 but skips the region B_e(H)α; when e(H)α ≥ d, that region covers the full symmetry-breaking region B_d.Thus symmetry breaking is removed everywhere in this case, consistent with the α = 1 result of Chatterjee and Diaconis.Source: §4 · p. 19

5. Densities of linear hypergraphs in random hypergraphs

The section extends the Chatterjee–Varadhan large-deviation framework to linear hypergraph densities and identifies the symmetry criterion for regular linear hypergraphs. The criterion is governed by whether (r^d, h_p(r)) lies on the convex minorant of x ↦ h_p(x^(1/d)).

Replica symmetry

  • For a d-regular linear hypergraph, the constant function r is the unique variational minimizer when (r^d, h_p(r)) lies on the convex minorant of x ↦ h_p(x^(1/d)).The proof uses the large-deviation variational problem and a generalized Hölder inequality.Source: §5 · pp. 20, 23

Scope

  • The framework is restricted to linear hypergraphs because a corresponding counting lemma is unavailable for general hypergraphs in this setting.The authors state that the basic framework suffices for controlling densities of linear hypergraphs.Source: §5 · p. 21

Large deviations

  • The Chatterjee–Varadhan framework extends to linear hypergraphs, yielding a large deviation principle with rate function h_p.The extension outlines modifications and omits full details because the changes to the original proofs are mostly straightforward.Source: §5 · pp. 21–22

Hypergraph graphon framework

  • Densities of fixed linear hypergraphs are continuous in the hypergraph cut topology, enabling their use in the large-deviation framework.The section also establishes compactness of the corresponding hypergraph graphon space.Source: §5 · p. 22

Conditional concentration

  • When the minimizing class has a unique element, the conditional hypergraph distribution converges to that minimizer as n grows.The minimizers form a nonempty compact set, with an exponential concentration bound stated in the theorem.Source: §5 · p. 22

Symmetry breaking

  • Outside that convex-minorant condition, a function f can have hypergraph density above the target while having lower rate-function cost than the constant function r.Thus the symmetric candidate is not a minimizer in this regime.Source: §5 · pp. 21, 23

6. Graph homomorphism inequalities

The section gives a short proof of a graph homomorphism inequality for regular bipartite graphs. The proof follows directly from generalized Hölder and avoids the entropy and limiting arguments used in earlier proofs.

Inequality

  • For a d-regular bipartite graph G and a graph H that may contain loops, the homomorphism inequality extends to graphons and is tight for disjoint unions of copies of K_d,d.The graphon form applies to any d-regular bipartite G and f in W0.Source: §6 · p. 23

Proof

  • Generalized Hölder gives a short proof of the inequality without entropy or limiting arguments.The authors note that previously known proofs used entropy.Source: §6 · p. 23

Scope

  • The inequality does not extend to all d-regular graphs: K3 with the graphon from the 2 × 2 identity matrix is a counterexample.An extension to non-bipartite graphs is stated only for certain families of graphons.Source: §6 · p. 23

7. Open problems

The open problems concern extensions beyond the settings with identified phase boundaries, and unresolved structure of minimizers and symmetry breaking in several regimes.

7. Open problems

  • Sparse random graphs and densities of general, not necessarily linear, hypergraphs remain settings for extending the large-deviation theory.Such extensions may require sparse versions of the regularity lemma.Source: §7 · p. 24

Minimizers of the variational problem.

  • No variational-problem solutions are known anywhere in the symmetry-breaking phase, and the rate is unknown at every point there.Whether minimizers are always 2-step graphons remains open.Source: Minimizers of the variational problem · p. 24

Phase boundary for non-regular graphs.

  • For non-regular subgraph densities, the phase boundary remains unknown, and matching boundaries for replica symmetry are not established.The authors suggest a modification of Lemma 3.4 might establish symmetry breaking for some, perhaps all, such deviations.Source: Phase boundary for non-regular graphs · p. 24

Lower-tail phase transition.

  • For bipartite H, lower-tail replica symmetry follows if H satisfies Sidorenko’s conjecture, but whether all bipartite graphs do so is open.For non-bipartite H, symmetry breaking occurs for some lower-tail parameters, but the complete phase diagram is unknown.Source: Lower-tail phase transition · p. 24

Symmetry breaking in exponential random graphs.

  • The plotted symmetry-breaking region for exponential random graphs may not be complete; characterizing the full replica-symmetric parameter set remains open.The open characterization concerns triples (α, β1, β2) in Theorem 1.3.Source: Symmetry breaking in exponential… · p. 24

Appendix A. The convex minorant of hp(x1/γ)

Appendix A characterizes convexity and the convex minorant of hp(x^(1/γ)), then uses that geometry to describe the regions Bγ. For γ>1 below a threshold, the function has a concave middle segment replaced by a common lower tangent.

Convex minorant

  • When the function is nonconvex, its convex minorant replaces the middle segment with the common lower tangent touching the curve at two points.The tangent contacts are denoted by q(γ,p) in the appendix.Source: Appendix A · pp. 24, 27

Figures

  • Figure 8’s function plots are illustrative and not to scale, while the phase-diagram plots are drawn to scale.This distinction applies to the plots described in the figure caption.Source: Appendix A · p. 25

Regions Bγ

  • Each Bγ consists of parameter points outside the convex-minorant boundary; its vertical sections are intervals, and Bγ has a rotated-V shape.For γ > γ′, Bγ strictly contains Bγ′; the appendix derives this ordering by transforming the plots with x = u^(γ′/γ).Source: Appendix A · pp. 25, 28

Convexity of hp(x^(1/γ))

  • For 0 < γ ≤ 1, hp(x^(1/γ)) is convex; for γ > 1, convexity depends on p, with two inflection points and a concave middle region below a threshold.The threshold is denoted p0(γ).Source: Appendix A · pp. 24–25

Convex minorant

  • A secant below the curve that is tangent at neither endpoint lies strictly above the lower common tangent, bounding its contact points.This is the geometric criterion in Lemma A.3.Source: Appendix A · p. 27

Related papers

Loading 1210.7013v2…