On replica symmetry of large deviations in random graphs

Introduction

The following question was raised by Chatterjee and Varadhan concerning large deviations in $\mathcal{G}(n,p)$, the Erdős-Rényi random graph on $n$ vertices with edge density $p$.

Fix $0<p<r<1$ and let $G_{n}$ be an instance of $\mathcal{G}(n,p)$ conditioned on the rare event of having at least as many triangles as a typical instance of $\mathcal{G}(n,r)$. Is it the case that as $n\to\infty$ the graph $G_{n}$ is close in cut-distance to a typical $\mathcal{G}(n,r)$ graph?

(A more formal statement, including the definition of the graph cut-metric, is postponed to §1.1.) This amounts to asking whether the likely reason for too many triangles is an overwhelming number of edges, uniformly distributed, or some fewer edges arranged in a special structure, e.g., a clique. Dubbed replica symmetry and symmetry breaking, resp., the dichotomy between these scenarios turns out to depend on $p$ and $r$. Intriguingly, it was known that for small enough $p$ there are at least two phase transitions as $r$ increases from $p$ to $1$, with symmetry replica near the two endpoints.

In this work we analyze the variational problems arising from the framework of Chatterjee and Varadhan and obtain a full answer for the question above, as depicted in Fig. 1. More generally, we identify the phase diagram for upper tails of any fixed regular subgraph and derive related results in other random graph settings, e.g., exponential random graphs, random hypergraphs, etc.

Large deviations for subgraph densities in random graphs have been extensively studied (see, e.g., as well as and the references therein). A representing example which drew significant attention is upper tails of triangle counts, i.e., estimating the probability that $\mathcal{G}(n,p)$ has at least $\binom{n}{3}r^{3}$ triangles where $r=(1+\eta)p$ for fixed $\eta>0$ (allowing $p$ to vary with $n$), a problem whose understanding is still incomplete. The order of the rate function (the normalized logarithm of this probability) when $p\to 0$ was only very recently settled: Chatterjee and DeMarco and Kahn independently established it to be $n^{2}p^{2}\log(1/p)$ when $p\gtrsim\log n/n$, and yet the exact rate function remains unknown in this range of $p$. We now turn to what was known for fixed $p$, our focus in this paper.

Clearly, if the total number of edges in $\mathcal{G}(n,p)$ deviates to $m\sim\binom{n}{2}r$ then one will arrive at a random graph with $m$ uniformly distributed edges featuring the desired number of triangles. Thus, the large deviation rate function for encountering $\binom{n}{3}r^{3}$ triangles in $\mathcal{G}(n,p)$ is at most $h_{p}(r)$, where

is the rate function associated to the binomial distribution with probability $p$. However, it is possible that other configurations with broken symmetry would give rise to lower rate functions.

As an application of Stein’s method for concentration inequalities, Chatterjee and Dey found a range of $(p,r)$ where the large deviation rate function for triangles is equal to $h_{p}(r)$, namely when $p\geq 2/(2+e^{3/2})\approx 0.31$ or when $r$ is suitably close either to $p$ or to $1$. This symmetry region was explicitly stated in [8, Theorem 4.3] as all pairs $(p,r)$ where $(r^{3},h_{p}(r))$ lies on the convex minorant of $x\mapsto h_{p}(x^{1/3})$. The breakthrough work of Chatterjee and Varadhan introduced a remarkable general framework for large deviation principles in $\mathcal{G}(n,p)$ via Szemerédi’s regularity lemma and the theory of graph limits by Lovász et al. . It expressed the large deviation rate function, and moreover the structure of the random graph conditioned on the large deviation, in terms of a variational problem on graphons, the infinite-dimensional limit objects for graph sequences.

Although often this variational problem is untractable, for triangles in the mentioned range of $(p,r$) it was shown in to have a unique and symmetric solution. To formalize this symmetry, we say a graph $G$ is close in cut-distance to a typical $\mathcal{G}(n,r)$ graph if all induced subgraphs on a linear number of vertices have edge density close to $r$. More precisely, for a graph $G$ and $r\in$ let

where $e_{G}(A,B)$ is the number of pairs $(a,b)\in A\times B$ with $ab\in E(G)$. Chatterjee and Varadhan showed that, in the above range of $(p,r)$, if $G_{n}\sim\mathcal{G}(n,p)$ is conditioned to have at least $\binom{n}{3}r^{3}$ triangles then $\delta_{\square}(G_{n},r)\to 0$ in probability as $n\to\infty$. The function $x\mapsto h_{p}(x^{1/3})$ governing that region is the natural candidate for the phase boundary as the cube-root accounts for the 3 edges of the triangle (see, e.g., [15, §4.5.2] for related literature), and indeed Chatterjee and Varadhan asked whether this precisely characterizes the full replica symmetric phase. As it turns out, however, the replica symmetric phase is strictly larger, being governed instead by $x\mapsto h_{p}(\sqrt{x})$. (See Fig. 1.)

For any graph $G$ let $e(G)=\left\lvert E(G)\right\rvert$, and for any two graphs $G$ and $H$ let $\hom(H,G)$ denote the number of homomorphisms from $H$ to $G$ (i.e., maps $V(H)\to V(G)$ that carry edges to edges). Let

be the probability that a random map $V(H)\to V(G)$ is a graph homomorphism. We now state our main result on the phase diagram for large deviations in densities of $d$-regular subgraphs.

Fix $0<p\leq r<1$ and let $H$ be a fixed $d$-regular graph for some $d\geq 2$. Let $G_{n}\sim\mathcal{G}(n,p)$ be the Erdős-Rényi random graph on $n$ vertices with edge probability $p$.

If the point $(r^{d},h_{p}(r))$ lies on the convex minorant of the function $x\mapsto h_{p}(x^{1/d})$ then

and furthermore, for every $\varepsilon>0$ there exists some $C=C(H,\varepsilon,p,r)>0$ such that for all $n$,

If the point $(r^{d},h_{p}(r))$ does not lie on the convex minorant of the function $x\mapsto h_{p}(x^{1/d})$ then

and furthermore, there exist $\varepsilon,C>0$ such that for all $n$,

In particular, when $d=2$, case (ii) occurs if and only if $p<\left[1+(r^{-1}-1)^{1/(1-2r)}\right]^{-1}$.

The boundary curves for various values of $d$ are plotted in Fig. 2. It is easy to verify (Lemma A.1) that the rightmost point in the curve for $d$-regular subgraphs is (p,r)=\big{(}\frac{d-1}{d-1+e^{d/(d-1)}},\frac{d-1}{d}\big{)}.

We give an analogous result for large deviations of the spectral radius of an Erdős-Rényi random graph. The phase boundary in this case coincides with that of triangles.

Fix $0<p\leq r<1$. Let $G_{n}\sim\mathcal{G}(n,p)$ be an Erdős-Rényi random graph on $n$ vertices with edge probability $p$, and let $\lambda_{1}(G_{n})$ denote the largest eigenvalue of its adjacency matrix.

If $p\geq\left[1+(r^{-1}-1)^{1/(1-2r)}\right]^{-1}$ then

and furthermore, for every $\varepsilon>0$ there exists some $C=C(\varepsilon,p,r)>0$ such that for all $n$,

If $p<\left[1+(r^{-1}-1)^{1/(1-2r)}\right]^{-1}$ then

and furthermore, there exist $\varepsilon,C>0$ such that for all $n$,

Both theorems are proved through an analysis of the graphon variational problems rising from the framework of Chatterjee and Varadhan . We show that throughout the replica symmetric region its unique solution is the symmetric one (a consequence of a generalized form of Hölder’s inequality), whereas elsewhere one can construct graphons that outperform the symmetric candidate. Note that Theorem 1.2 addresses spectral large deviations, whereas the framework of was tailored for subgraph densities (the recent work broadens it to general random matrix properties with respect to an appropriately defined spectral distance. Here we consider concretely large deviations in the spectral norm of random graphs). Fortunately, the results of easily extend to a wide family of graph parameters with respect to the cut-metric, including the operator norm, the extension of the (normalized) spectral norm to the space of graphons. This generalization is detailed in §2.

2. Exponential random graphs

We now turn our attention to a different random graph model, the basic setting of which assigns a probability $p_{\beta}(G)$ to every graph $G$ on $n$ labeled vertices as a function of its edge density $t(K_{2},G)$, its triangles density $t(K_{3},G)$ and a weight vector $\beta=(\beta_{1},\beta_{2})$ for these two quantities.The general model allows for an arbitrary (fixed) collection of subgraphs. While the majority of our arguments can be extended to the general setting, we focus on the two-term model for simplicity and clarity. Namely, the graph $G$ appears with the following probability:

where $Z_{n}$ is a normalizing factor (the partition function). When $\beta_{2}>0$ the model favors graphs with more triangles whereas triangles are discouraged for $\beta_{2}<0$. There is a rich literature on both flavors of the model, motivated in part by applications in social networking: the reader is referred to as well as and the references therein.

As shown by Bhamidi, Bresler and Sly and Chatterjee and Diaconis , when $\beta_{2}\geq 0$ and $n$ is large, a typical random graph drawn from the distribution has a trivial structure — essentially the same one as an Erdős-Rényi random graph with a suitable edge density. This somewhat disappointing conclusion accounts for some of the practical difficulties with statistical parameter estimation for such models. It was further shown in that if we allow $\beta_{2}$ to be sufficiently negative, then the model does behave appreciably differentially from an Erdős-Rényi model. In this part of our work we focus on the case $\beta_{2}>0$, and propose a natural generalization that will enable the model to exhibit a nontrivial structure instead of the previously observed Erdős-Rényi behavior.

Consider the exponential random graph model which includes an additional exponent $\alpha>0$ in the exponent of the triangle density term:

We will show that this model exhibits a symmetry breaking phase transition even when $\beta_{2}>0$. When $\alpha\geq 2/3$, the generalized model features the Erdős-Rényi behavior, similar to the previously observed case of $\alpha=1$. However, for $0<\alpha<2/3$, there exist regions of values of $(\beta_{1},\beta_{2})$ for which a typical random graph drawn from this distribution has symmetry breaking. As was the case for Theorems 1.1 and 1.2, rather than just triangles we prove this result for any $d$-regular graph $H$.

Suppose $0<\alpha<d/e(H)$ and $\beta_{1}\geq\log(d-1)-d/(d-1)$. Then there exists $0<u^{*}<1$ such that for every $\varepsilon>0$ there is a $C>0$ such that $\delta_{\square}(G_{n},u^{*})\to 0$ almost surely as $n\to\infty$.

Suppose $0<\alpha<d/e(H)$ and $\beta_{1}<\log(d-1)-d/(d-1)$. Then there exists an open interval of values $\beta_{2}>0$ with the property that there exist $\varepsilon,C>0$ such that for all $n$,

3. Linear hypergraphs

Theorem 5.1 (see §5) extends Theorem 1.1 to the setting of random hypergraphs. A $k$-uniform hypergraph $G$ consists of a set $V(G)$ of vertices and a set $E(G)$ of hyperedges, where each hyperedges is a $k$-element subsets of $V(G)$. It is said to be $d$-regular if every vertex is incident to exactly $d$ edges, and linear if every two vertices are incident to at most one common hyperedge (see Fig. 4 for examples of $d$-regular 3-uniform linear hypergraphs). The random hypergraph $\mathcal{G}^{(k)}(n,p)$ is formed by starting with $n$ vertices and adding $k$-element subset of the vertices as a hyperedge independently with probability $p$.

In order to generalize our arguments to large deviations in the density of $H$, an arbitrary $d$-regular linear hypergraph, one must first extend the theory developed by Chatterjee and Varadhan to $k$-uniform hypergraphs. Thanks to the linearity of the hypergraph $H$ there is a simple extension of Szemerédi’s regularity lemma to hypergraphs that behaves well with respect to the density of $H$.

4. Graph homomorphisms

Alon conjectured in 1991 that the number of independent sets in a $d$-regular graph $G$, denoted $i(G)$, satisfies $i(G)\leq i(K_{d,d})^{|V(G)|/(2d)}$, i.e., it is maximized when $G$ is a union of complete bipartite graphs $K_{d,d}$. Kahn verified this when $G$ is bipartite using an ingenious application of the entropy method (specifically, Shearer’s inequality). This result was thereafter extended by the second author to all $d$-regular graphs via an elementary bijection. Using the entropy method of Kahn, Galvin and Tetali extended to graph homomorphisms:

Let $G$ be a simple $d$-regular bipartite graph, and let $H$ be a graph, possibly containing loops. We have

5. Organization

In §2 we review graph limits as well as the large deviation principle for random graphs developed by Chatterjee and Varadhan. In §3 we apply the machinery of Chatterjee and Varadhan to prove Theorems 1.1 and 1.2, determining the phase diagram for large deviations of subgraph densities and the largest eigenvalue in $\mathcal{G}(n,p)$, resp. Section 4 focuses on exponential random graphs and gives the proof of Theorem 1.3. In §5 we extend Theorem 1.1 to densities of linear hypergraphs in random hypergraphs. Section 6 contains the short new proof of the inequalities of Kahn and Galvin-Tetali (Theorem 1.4). Finally, in §7 we discuss some open problems.

Graph limits and the framework of Chatterjee-Varadhan

The theory of Chatterjee-Varadhan reduces the problem of determining the rate function for large deviations in dense random graphs to solving a prescribed variational problem in graph limits. We will review the required definitions from graph limit theory and then describe the results of in the broader context of “nice” graph parameters, generalizing subgraph counts.

(We shall omit the domain of integration when there is no ambiguity.) Any simple graph $G$ on vertices $\left\{1,2,\dots,n\right\}$ can be represented as a graphon $f^{G}$ by

In particular, $t(H,G)=t(H,f^{G})$ for any two graphs $H$ and $G$.

A sequence of graphs $\left\{G_{n}\right\}_{n\geq 1}$ is said to converge if the sequence of subgraph densities $t(H,G_{n})$ converges for every fixed finite simple graph $H$. It was shown in that for any such convergent graph sequence there is a limit object $f\in\mathcal{W}_{0}$ such that $t(H,G_{n})\to t(H,f)$ for every fixed $H$. Conversely, any $f\in\mathcal{W}_{0}$ arises as a limit of a convergent graph sequence.

We will consider several norms on $\mathcal{W}$, beginning with the standard $L^{p}$ norm

Each $f\in\mathcal{W}$ can be viewed as a Hilbert-Schmidt kernel operator $T_{f}$ on $L^{2}()$ by

and the operator norm for $f$ is then given by

As $T_{f}$ is self-adjoint, its operator norm is equal to its spectral radius (see, e.g., [40, Thm. 12.25]).

The cut-norm on $\mathcal{W}$ is given by

where the two suprema are equal since one only needs to consider $\{0,1\}$-valued $u$ and $v$ by the linearity of the integral. The second definition is useful for giving upper bounds using the cut-norm.

For any measure-preserving map $\sigma\colon\to$ and $f\in\mathcal{W}$, define $f^{\sigma}\in\mathcal{W}$ to be given by $f^{\sigma}(x,y)=f(\sigma(x),\sigma(y))$. We define the cut-distance on $\mathcal{W}$ by

where $\sigma$ ranges over all measure-preserving bijections on $$. For the case of graphons this gives a pseudometric space$(\mathcal{W}_{0},\delta_{\square})$, which can be turned into a genuine metric space$\widetilde{\mathcal{W}}_{0}$, equipped with the same cut-metric, by taking a quotient w.r.t. the equivalence relation$f\sim g$iff$\delta_{\square}(f,g)=0$. The following theorem can be viewed as a topological interpretation of Szemerédi’s regularity lemma.

The metric space $(\widetilde{\mathcal{W}}_{0},\delta_{\square})$ is compact.

It was shown in that a sequence of graphs $\left\{G_{n}\right\}_{n\geq 1}$ converges in the sense of subgraph densities if and only if the sequence of graphons $f^{G_{n}}\in\mathcal{W}_{0}$ converge in $\mathcal{W}_{0}$ w.r.t. the cut-distance. Equivalently, the topology on $\mathcal{W}_{0}$ induced by $\delta_{\square}$ is the weakest topology that is continuous w.r.t. the subgraph densities $t(H,\cdot)$ for every $H$. This underlines one of the reasons making the cut-metric topology a natural choice for the space of graphons.

2. Graph parameters in the cut-metric topology

We shall focus on graph parameters whose extensions to the space of graphons behave well under the cut-metric topology. One example of such a graph parameter is the subgraph density $t(H,\cdot)$ for an arbitrary finite simple graph $H$, which was defined in §2.1 directly on the full space of graphons such that $t(H,G)=t(H,f^{G})$ for any graph $G$. A crucial feature of $t(H,\cdot)$ is being continuous w.r.t. the cut-metric (), related to the existence of a “counting lemma” in the regularity lemma literature. This will be a prerequisite for applying the large deviations machinery of Chatterjee and Varadhan.

Another way to state the local extrema condition is that if $f\in\mathcal{W}_{0}$ is not a global maximum (resp. minimum) of $\tau$ then for every $\varepsilon>0$ there exists $g\in\mathcal{W}_{0}$ with $\left\lVert f-g\right\rVert_{\infty}<\varepsilon$ and $\tau(g)>\tau(f)$ (resp. $\tau(g)<\tau(f)$). This technical condition will later imply the continuity of the rate function.

Since the metric space $(\widetilde{\mathcal{W}}_{0},\delta_{\square})$ is compact and path-connected, the image of $\tau$ as above is a finite closed interval. In particular, its maximum is attained by a non-empty closed subset of $\widetilde{\mathcal{W}}_{0}$.

For any fixed finite simple graph $H$, the subgraph density $t(H,\cdot)$ is a nice graph parameter. As mentioned above, $t(H,\cdot)$ is continuous w.r.t. $\delta_{\square}$ and in fact the map $f\mapsto t(H,f)$ is Lipschitz-continuous in the metric $\delta_{\square}$ ([4, Theorem 3.7]). The local extrema condition is fulfilled since the function $g^{+}=\min\left\{f+\varepsilon,1\right\}$ satisfies $t(H,g^{+})>t(H,f)$ unless $t(H,f)=1$, and similarly $g^{-}=(1-\varepsilon)f$ has $t(H,g^{-})<t(H,f)$ unless $t(H,f)=0$.

The next two examples are of graph parameters that do not meet the criteria of Definition 2.2.

Let $\tau$ be the function that maps a weighted graph $G$ on $n$ vertices with adjacency matrix $A_{G}$ to the normalized Frobenius norm $\left\lVert A_{G}\right\rVert_{\textrm{F}}/n$. Then $\tau$ is discontinuous in $(\widetilde{\mathcal{W}}_{0},\delta_{\square})$ and therefore is not nice. Indeed, fix $0<p<1$ and let $G_{n}\sim\mathcal{G}(n,p)$. The sequence $G_{n}$ is known to converge in $\widetilde{\mathcal{W}}_{0}$ almost surely to the constant graphon $p$ (see [4, Theorem 4.5]), whose Frobenius norm is $p$. In contrast to this limiting value, $\left\lVert A_{G_{n}}\right\rVert_{\textrm{F}}/n=\left\lVert f^{G_{n}}\right\rVert_{2}\to\sqrt{p}$ almost surely.

Despite being continuous w.r.t. $\delta_{\square}$ as well as monotone, the max-cut density is not nice. The continuity of $\tau$ follows from the fact $\left\lvert\tau(f)-\tau(g)\right\rvert\leq\delta_{\square}(f,g)$, as any cut for either $f$ or $g$ translates into a cut for the other with value differing by at most $\delta_{\square}(f,g)$. To see that $\tau$ does not satisfy the local maxima condition, let $f$ be the graphon defined to be $1$ on $[0,\frac{1}{3}]\times[\frac{1}{3},1]\cup[\frac{1}{3},1]\times[0,\frac{1}{3}]$ and 0 elsewhere. We have $\tau(f)=\frac{2}{9}$, induced by $U=[0,\frac{1}{3}]$. This is not the global maximum for $\tau$, which is $\frac{1}{4}$ for the constant function $1$. However, we claim that $f$ is a local maximizer of $\tau$ with respect to the $L^{\infty}$-topology. By monotonicity, showing that $\tau(g)=\frac{2}{9}$ for the function $g=\min\left\{f+\frac{1}{2},1\right\}$ will imply that $\tau(f_{0})\leq\tau(g)=\tau(f)$ for any $f_{0}$ with $\left\lVert f_{0}-f\right\rVert_{\infty}\leq\frac{1}{2}$. Indeed, if $\mu(U\cap[0,\frac{1}{3}])=a$ and $\mu(U\cap[\frac{1}{3},1])=b$, where $\mu$ is Lebesgue measure, then the cut density induced by $U$ for $g$ is equal to $\frac{1}{2}a(\frac{1}{3}-a)+\frac{1}{2}b(\frac{2}{3}-b)+a(\frac{2}{3}-b)+b(\frac{1}{3}-a)$, which is maximized at $(a,b)=(0,\frac{2}{3})$ and $(a,b)=(\frac{1}{3},0)$.

We will see in §3.2 (see Lemma 3.6) that, in contrast to the Frobenius norm, the spectral norm (the focus of Theorem 1.2) does behave well under the cut-metric topology, thus qualifying for an application of the large deviation theory of Chatterjee and Varadhan.

3. Large deviations for random graphs

An important feature of $h_{p}$ is that it is a convex function on $$and hence lower-semicontinuous on$\widetilde{\mathcal{W}}_{0}$ with respect to the cut-metric topology ([8, Lem. 2.1]).

Using Szemerédi’s regularity lemma as well as tools from graph limits, Chatterjee and Varadhan proved the following large deviation principle for random graphs.

and for any open $U\subseteq\widetilde{\mathcal{W}}_{0}$,

Since $h_{p}$ is lower-semicontinuous on $\widetilde{\mathcal{W}}_{0}$, the infimum in (2.1) is always attained.

The following result was stated in [8, Thm 4.1 and Prop. 4.2] for the graph parameter $\tau=t(K_{3},\cdot)$. We state its generalization to the class of nice graph parameters as per Definition 2.2.

Let $F^{*}$ be the set of minimizers for (2.1) and let $\widetilde{F}^{*}$ be its image in $\widetilde{\mathcal{W}}_{0}$. Then $\widetilde{F}^{*}$ is a non-empty compact subset of $\widetilde{\mathcal{W}}_{0}$. Moreover, for each $\varepsilon>0$ there exists $C=C(\tau,\varepsilon,p,t)>0$ so that for all $n$,

In particular, if $\widetilde{F}^{*}=\{f^{*}\}$ for some $f^{*}\in\widetilde{\mathcal{W}}_{0}$ then the conditional distribution of $G_{n}$ given the event $\tau(G_{n})\geq t$ converges to the point mass at $f^{*}$ as $n\to\infty$.

Observe that by considering $-\tau$ (also a nice graph parameter) one obtains the same result for lower tail deviations. The intuition behind the second part of Theorem 2.7 is that the probability that $\delta_{\square}(G_{n},\widetilde{F}^{*})\geq\varepsilon$ conditioned on $\tau(G_{n})\geq t$ can be again computed using Theorem 2.6 and shown to be exponentially smaller than that of the probability of the event $\tau(G_{n})\geq t$.

The proof of Theorem 2.7 is a straightforward extension of the arguments of [8, Thm. 4.1] to nice graph parameters. A technical condition needed to complete the proof of Theorem 2.7 is given by the following lemma, key to which are the attributes of a nice graph parameter.

The phase diagram for subgraph densities and the spectral radius

In this section we prove Theorem 1.1, characterizing the phase diagram of upper tails (replica symmetry vs. symmetry breaking) of the density of a fixed $d$-regular subgraph.

Establishing the replica symmetric phase will hinge on a generalized form of Hölder’s inequality which appeared in . We include its short proof for completeness.

In particular, when $p_{i}=d$ for every $i\in[m]$ we have $\int\prod_{i=1}^{m}|f_{i}|\ d\mu\leq\prod\left(\int|f_{i}|^{d}\ d\mu_{A_{i}}\right)^{1/d}$.

The proof carries by induction on $n$ with the trivial base case of $n=0$. By Fubini’s theorem,

where the argument of each $f_{i}$ is the restriction of $x\in\Omega$ to the coordinates of $A_{i}$, denoted by $x_{A_{i}}$. Hölder’s inequality (along with Jensen’s inequality if $\sum_{i:n\in A_{i}}(1/p_{i})$ is less than $1$) implies that

Placing this in the context of subgraph densities, as an immediate corollary of Theorem 3.1 (in the special case that $p_{i}=d$ for all $i$) we have the following inequality.

Let $H$ be a graph whose maximum degree is at most $d$, and let $f\in\mathcal{W}$. Then

Recall that Theorem 2.7 reduces the problem of finding the phase boundary to determining whether the constant function $r$ is a solution for the variational problem of minimizing $h_{p}(f)$ over $f\in\mathcal{W}_{0}$ subject to $t(H,f)\geq r^{e(H)}$, where $H$ is some fixed graph. In light of the above corollary, it is important to estimate $h_{p}(f)$ for functions $f\in\mathcal{W}_{0}$ with $\left\lVert f\right\rVert_{d}=r$, as addressed next.

Let $0<p<1$ and let $f\in\mathcal{W}_{0}$. Suppose that $d\geq 1$ and $0<r<1$ are such that the point $(r^{d},h_{p}(r))$ lies on the convex minorant of $x\mapsto h_{p}(x^{1/d})$. If in addition either

$p<r<1$ and $\left\lVert f\right\rVert_{d}\geq r$, or

$0<r<p$ and $\left\lVert f\right\rVert_{d}\leq r$,

then $h_{p}(f)\geq h_{p}(r)$, with equality occurring if and only if $f\equiv r$.

Let $\psi(x)=h_{p}(x^{1/d})$ and let $\hat{\psi}$ be the convex minorant of $\psi$. By Jensen’s inequality,

The fact that $h_{p}(x)$ is decreasing along $[0,p]$ and increasing along $[p,1]$ (see §A) implies that under either of the assumptions in Part (a) and Part (b) we have $h_{p}(\left\lVert f\right\rVert_{d})\geq h_{p}(r)$, hence $h_{p}(f)\geq h_{p}(r)$. Since $\hat{\psi}$ is not linear in any neighborhood of $r^{d}$, equality can occur if and only if $f=r$. ∎

The final element needed for the proof of Theorem 1.1 is a construction that outperforms the constant graphon in the symmetry breaking regime. This is achieved by the following lemma.

Let $H$ be a $d$-regular graph. Fix $0<p\leq r<1$ so that $(r^{d},h_{p}(r))$ is not on the convex minorant of $x\mapsto h_{p}(x^{1/d})$. Then there exists $f\in\mathcal{W}_{0}$ with $t(H,f)>r^{e(H)}$ and $h_{p}(f)<h_{p}(r)$.

Since $(r^{d},h_{p}(r))$ does not lie on the convex minorant of $x\mapsto h_{p}(x^{1/d})$, there necessarily exist $0\leq r_{1}<r<r_{2}\leq 1$ such that the point $(r^{d},h_{p}(r))$ lies strictly above the line segment joining $(r_{1}^{d},h_{p}(r_{1}))$ and $(r_{2}^{d},h_{p}(r_{2}))$. Letting $s$ be such that

noting that for $a<1-b$ for any sufficiently small $\varepsilon$. Define $f_{\varepsilon}\in\mathcal{W}_{0}$ by

(See Fig. 5 for an illustration of this construction.) We claim that

Indeed, the only embeddings of $H$ that have values different from $r^{e(H)}$ are those where at least one vertex of $H$ is mapped to $I_{1}\cup I_{2}$. Since $a$ and $b$ are both $O(\varepsilon^{2})$, in order to compute $t(H,f_{\varepsilon})-r^{e(H)}$ up to an $O(\varepsilon^{4})$ error we need only consider embeddings of $H$ where precisely one vertex gets mapped to $I_{1}\cup I_{2}$. Denote this vertex of $H$ by $u$, and observe that if $u$ is mapped to $I_{1}$ then the contribution to $t(H,f_{\varepsilon})-r^{e(H)}$ is $(r_{1}^{d}-r^{d})r^{e(H)-d}$ since $H$ is $d$-regular. Similarly, if $u$ is mapped to $I_{2}$ then the contribution is $(r_{2}^{d}-r^{d})r^{e(H)-d}$. Putting everything together yields (3.2).

Recalling that $r_{2}>r$ and plugging the last equation in (3.2) it now follows that $t(H,f_{\varepsilon})>r^{e(H)}$ for any sufficiently small $\varepsilon>0$. At the same time, we also have

Revisiting (3.1) we conclude that $h_{p}(f_{\varepsilon})<h_{p}(r)$ for any sufficiently small $\varepsilon>0$. ∎

We now have all the ingredients needed for establishing the phase diagram of upper tail deviations for subgraph densities.

For Part (i), by applying Theorem 2.7 to the graph parameter $t(H,\cdot)$, it suffices to show that the constant function $r$ is the unique element $f\in\mathcal{W}_{0}$ minimizing $h_{p}(f)$ subject to $t(H,F)\geq r^{e(H)}$. Indeed, by Corollary 3.2, $t(H,F)\geq r^{e(H)}$ implies that $\left\lVert f\right\rVert_{d}\geq r$, and by Lemma 3.3 Part (a), $h_{p}(f)\geq h_{p}(r)$ with equality if and only if $f$ is the constant function $r$.

To prove Part (ii), let $F^{*}\subset\widetilde{\mathcal{W}}_{0}$ be the set of minimizers for the variational problem (2.1) with the graph parameter $t(H,\cdot)$. Then $F^{*}$ does not contain the constant function $r$ by Lemma 3.4, nor does it contain any constant function of value $r^{\prime}\neq r$ (when $r^{\prime}>r$ one has $h_{p}(r^{\prime})>h_{p}(r)$, whereas if $r^{\prime}<r$ then $t(H,f)<r^{e(H)}$). Let $\widetilde{\mathcal{C}}\subset\widetilde{\mathcal{W}}_{0}$ be the set of constant graphons. Since $F^{*}$ and $\widetilde{\mathcal{C}}$ are disjoint and both are compact, $\delta_{\square}(F^{*},\widetilde{\mathcal{C}})>0$. The desired result follows from applying Theorem 2.7 with $\varepsilon=\delta_{\square}(F^{*},\widetilde{\mathcal{C}})/2$.

When $d=2$, the phase boundary is explicitly given by Lemma A.2, thus concluding the proof. ∎

One can also ask what the phase diagram is for lower tail deviations of subgraph densities. We next show that for certain bipartite graphs there is replica symmetry everywhere for lower tails.

A beautiful conjecture of Erdős and Simonovits and Sidorenko (from here on referred to as Sidorenko’s conjecture) states that every bipartite graph $H$ satisfies $t(H,G)\geq t(K_{2},G)^{e(H)}$ for every graph $G$. The conjecture was verified for various graphs $H$ (e.g., trees, even cycles , hypercubes , bipartite graphs with one vertex complete to the other part ). As it turns out, for any such graph $H$ the lower tail deviations are always replica symmetric (no phase transition).

Fix $0<r\leq p<1$, let $G_{n}\sim\mathcal{G}(n,p)$ be the Erdős-Rényi random graph and let $H$ be a fixed bipartite graph for which Sidorenko’s conjecture holds. Then

and furthermore, for every $\varepsilon>0$ there exists some constant $C=C(H,\varepsilon,p,r)>0$ such that

Applying Theorem 2.7 with $-t(H,\cdot)$, it suffices to show that the constant function $r$ is the unique element $f\in\mathcal{W}_{0}$ minimizing $h_{p}(f)$ subject to $t(H,f)\leq r^{e(H)}$. Since $H$ satisfies Sidorenko’s conjecture, $t(H,f)\geq\left\lVert f\right\rVert_{1}^{e(H)}$ for all $f\in\mathcal{W}_{0}$. Thus, if $t(H,f)\leq r^{e(H)}$ then $\left\lVert f\right\rVert_{1}\leq r$, and so by Lemma 3.3 Part (b) (applied to the case $d=1$, noting that then $h_{p}(x^{1/d})$ is itself convex) we have $h_{p}(f)\geq h_{p}(r)$ with equality if and only if $f$ is the constant function $r$. ∎

2. Largest eigenvalue

In this section we prove Theorem 1.2, addressing the phase boundary for large deviations in the spectral norm. The proof will follow a similar route as the previous section, yet first we must show that the spectral norm is a nice graph parameter.

Let $u\in L^{2}()$ with $\left\lVert u\right\rVert_{2}=1$. By Cauchy-Schwarz we can infer that

For any fixed $x^{\prime},y^{\prime}$ we can let $v_{y^{\prime}}(x)=f(x,y^{\prime})$ and $w_{x^{\prime}}(y)=f(x^{\prime},y)$, thus rewriting the above as

with the last inequality justified by the fact that for any $g\in\mathcal{W}$ and $v,w\colon\to$ we have $\left|\int g(x,y)v(x)w(y)\ dxdy\right|\leq 4\left\lVert g\right\rVert_{\square}$ by the definition of the cut-norm, thereby establishing Eq. (3.3). (The factor of 4 above was due to splitting $v,w$ into positive and negative parts. Indeed, for $f\colon^{2}\to$ the bound in (3.3) remains valid without the factor of 4 in the right-hand side.)

Consider $f,g\in\widetilde{\mathcal{W}}_{0}$ and let $\sigma$ vary over all measure-preserving bijections on $$. We then have

In light of the above lemma, the variational problem under consideration in Theorem 1.2 becomes

We will need the following straightforward inequality relating the operator norm, $\left\lVert\cdot\right\rVert_{1}$ and $\left\lVert\cdot\right\rVert_{2}$.

For the left inequality, observe that since $f\geq 0$ we have that

The following lemma is the operator norm analogue of Lemma 3.4, providing a construction that beats the constant graphon in the symmetry breaking regime.

Recall that $f_{\varepsilon}(x,y)$ is $r$ except when $(x,y)\in(I_{0}\times I_{i})\cup(I_{i}\times I_{0})$ where it is $r_{i}$ for $i=1,2$. It now follows that for every $x\in I_{1}=[0,a]$

Similarly, for any $x\in I_{2}=[1-b,1]$ we have

Plugging in the facts that $r^{2}=sr_{1}^{2}+(1-s)r_{2}^{2}$ while $a=s\varepsilon^{2}$ and $b=(1-s)\varepsilon^{2}+\varepsilon^{3}$, we get that

where the strict inequality is valid for any sufficiently small $\varepsilon>0$ since $r_{2}>r$.

For Part (ii), similar to the proof of Part (ii) of Theorem 1.1 in §3.1, Lemma 3.8 implies that the set of minimizers of the variational problem (2.1) is disjoint from the set of constant graphons. We then apply Theorem 2.7 to conclude the proof, with the phase boundary given by Lemma A.2. ∎

The behavior of the lower tails deviations in the spectral norm is similar to that of the subgraph densities in Proposition 3.5, where replica symmetry is exhibited everywhere (no phase transition).

Let $0<r\leq p<1$. Let $G_{n}\sim\mathcal{G}(n,p)$ be the Erdős-Rényi random graph and let $\lambda_{1}(G_{n})$ denote the largest eigenvalue of its adjacency matrix. Then

and furthermore, for every $\varepsilon>0$ there is some $C=C(\varepsilon,p,r)>0$ such that for all $n$,

Exponential random graph models

Let us review the tools developed by Chatterjee and Diaconis to analyze exponential random graphs. Define

and for any graphon $f\in\mathcal{W}_{0}$ let

The following result from [7, Thm. 3.1 and Thm. 3.2] reduces the analysis of the exponential random graph model in the large $n$ limit to a variational problem. It was proven with the help of the theory developed by Chatterjee and Varadhan for large deviations in random graphs.

and the set $F^{*}\subset\widetilde{\mathcal{W}}_{0}$ of maximizers of this variational problem is nonempty and compact.

Let $G_{n}$ be a random graph on $n$ vertices drawn from the exponential random graph model defined by $\tau$, i.e., with distribution $Z_{n}^{-1}\exp\left(\binom{n}{2}\tau(\cdot)\right)$. Then for every $\eta>0$ there exists $C=C(\tau,\eta)>0$ such that for all $n$,

We say that the exponential random graph model has replica symmetry if the set of maximizers $F^{*}$ for the variational problem $\tau(f)-h(f)$ contains only constant functions, and we say that it has replica symmetry breaking if no constant function is a maximizer. Intuitively, Theorem 4.1 implies that when there is replica symmetry, for large $n$, the random graph behaves like an Erdős-Rényi random graph (or a mixture of Erdős-Rényi random graphs), while this is not the case when there is broken symmetry. More precisely we have the following result (see [7, Thm. 6.2]).

Continuing with Theorem 4.1. Let $\widetilde{\mathcal{C}}\subset\widetilde{\mathcal{W}}_{0}$ be the set of constant functions. If $F^{*}\cap\widetilde{\mathcal{C}}=\emptyset$ then there exist $C,\varepsilon>0$ such that for all $n$,

To prove Theorem 1.3 using the above tools, we need to analyze the following variational problem:

Here is the main result of this section, from which Theorem 1.3 follows by the results above.

If $0<\alpha<d/e(H)$ and $\beta_{1}\geq\log(d-1)-d/(d-1)$ then $\mathcal{E}$ has replica symmetry. Moreover, the variational problem (4.2) is maximized by a unique constant function.

If $0<\alpha<d/e(H)$ and $\beta_{1}<\log(d-1)-d/(d-1)$ then there exists an open interval of values $\beta_{2}>0$ for which $\mathcal{E}$ has broken symmetry, i.e., the set of maximizers of the variational problem (4.2) does not contain any constant function. Furthermore, this open interval can be taken to be $(\underline{\smash{\beta}}_{2},\overline{\beta}_{2})$ with $\underline{\smash{\beta}}_{2}=\underline{u}^{1-e(H)\alpha}h_{p}^{\prime}(\underline{u})/(e(H)\alpha)$ and $\overline{\beta}_{2}=\overline{u}^{1-e(H)\alpha}h_{p}^{\prime}(\overline{u})/(e(H)\alpha)$, where $(\underline{u}^{d},h_{p}(\underline{u}))$ and $(\overline{u}^{d},h_{p}(\overline{u}))$ are the two points where the lower common tangent of $x\mapsto h_{p}(x^{1/d})$ touches the curve for $p=1/(1+e^{-\beta_{1}})$.

When restricted only to constant functions in $\widetilde{\mathcal{W}}_{0}$, the variational problem (4.2) becomes the one-dimensional optimization problem

Note that for both (4.2) and (4.3) the supremum is in fact a maximum due to compactness. Let $u^{*}$ be the maximizer for (4.3). When there is replica symmetry, the maximum values attained in (4.2) and (4.3) are equal, and the exponential random graph behaves like an Erdős-Rényi random graph with edge density $u^{*}$. It is possible that there are two distinct maximizers $u^{*}$, in which case the model behaves like a (possibly trivial) distribution over two separate Erdős-Rényi models. In the work of Chatterjee and Diaconis , where the $\alpha=1$ case was considered, it was shown that $u^{*}$ as a function of $(\beta_{1},\beta_{2})$ experiences a discontinuity across a curve in the parameter space. Radin and Yin later showed that (when $\alpha=1$) the limiting free energy density $\psi$ from (4.1), as a function in the parameter space $(\beta_{1},\beta_{2})$, is analytic except on a first order phase transition curve ending in a critical point with second order phase transition. (See Fig. 3 in §1 for a plot of the location of the discontinuity in the $(\beta_{1},\beta_{2})$-phase diagram.)

Here we focus less on the discontinuity of $u^{*}$ and more on symmetry breaking. Nevertheless we shall start our analysis by giving a simple geometric interpretation of the discontinuity of $u^{*}$.

so that $\beta_{1}=\log\frac{p}{1-p}$, we absorb the linear term in (4.2) and (4.3) into the entropy term, at which point these two optimization problems respectively become

By a change of variables $u=x^{1/(e(H)\alpha)}$ in (4.5) we get the equivalent optimization problem

Observe that $x=x^{*}$ maximizes (4.6) iff the tangent to the curve defined by $x\mapsto h_{p}(x^{1/(e(H)\alpha)})$ at $x=x^{*}$ has slope $\beta_{2}$ and lies below the curve. Thanks to Lemma A.1 from the appendix, we know that $x\mapsto h_{p}(x^{1/\gamma})$ is convex if $0<\gamma\leq 1$ or if

If $0<e(H)\alpha\leq 1$ or if $e(H)\alpha>1$ and $p\geq p_{0}(e(H)\alpha)$ as defined in (4.7), then the optimization problem (4.3) is a maximized at a unique value of $u$. Otherwise, (4.3) is maximized at a unique $u$ except for a single value of $\beta_{2}$, where the maximum is attained at two distinct $u$’s.

We can also represent this jump of $u^{*}$ in the $(p,u)$-phase diagram as follows. For each $\gamma>0$, consider the region $\mathcal{B}_{\gamma}\subset^{2}$ containing all points $(p,u)$ such that $(u^{\gamma},h_{p}(u))$ does not lie on the convex minorant of $x\mapsto h_{p}(x^{1/\gamma})$. When $\gamma<1$ the region $\mathcal{B}_{\gamma}$ is empty, but otherwise it is nonempty. The geometric argument in the previous paragraph shows that $u$ can never appear as a maximizer to (4.5) if $(p,u)\in\mathcal{B}_{e(H)\alpha}$, but all other values of $u$ can. Thus, for a fixed $p=1/(1+e^{-\beta_{1}})$, as $\beta_{2}$ increases from $-\infty$ to $\infty$, the point $(p,u^{*})$ moves up continuously from in the $(p,u)$-phase diagram, and jumps over $\mathcal{B}_{e(H)\alpha}$ as it reaches it. Thereafter it resumes moving up until hitting 1. This process is illustrated on the left of Fig. 7 when $e(H)\alpha=3$, e.g., when $H=K_{3}$ and $\alpha=1$.

Turning to large deviations, we know from Lemma 3.4 that there is broken symmetry for the density of copies of a $d$-regular graph $H$ whenever we are in $\mathcal{B}_{d}$. It turns out that the same is true for the corresponding exponential random graph model given in (1.4). As we just saw though, one must remove $\mathcal{B}_{e(H)\alpha}$ from the possible solution space for $(p,u^{*})$. Whenever $\gamma<\gamma^{\prime}$ we have $\mathcal{B}_{\gamma}\subset\mathcal{B}_{\gamma^{\prime}}$ (see Lemma A.5), and consequently, if $e(H)\alpha\geq d$ then $\mathcal{B}_{e(H)\alpha}$ covers $\mathcal{B}_{d}$ and so the entire symmetry breaking phase is removed, leaving replica symmetry everywhere. This agrees with the results of Chatterjee and Diaconis for the case $\alpha=1$. However, when $e(H)\alpha<d$ it is possible to have $(p,u^{*})\in\mathcal{B}_{d}$, in which case the construction from Lemma 3.4 breaks the symmetry. This is shown on the right of Fig. 7 for the case $d=2$ and $e(H)\alpha=1.8$, e.g., for $H=K_{3}$ and $\alpha=0.6$.

The proof of Part (a) is essentially the same as the proof of Theorem 4.1 in the work of Chatterjee and Diaconis , except now we use the generalized Hölder’s inequality (Theorem 3.1) instead of the usual Hölder’s inequality.

Suppose that $\alpha\geq d/e(H)$. We first need to show that in this case the only maximizers for the variational problem (4.4) are constant functions. Applying Corollary 3.2, for any $f\in\widetilde{\mathcal{W}}_{0}$ we have

where the last inequality used the assumption on $\alpha$. This in turn is equal to

showing that the $\beta_{2}t(H,f)-h_{p}(f)$ is indeed maximized at constant functions. Furthermore, when $\beta_{2}u^{e(H)\alpha}-h_{p}(u)$ is maximized at a unique $u^{*}$, then equality holds in place of the above inequalities only for the constant function $f=u^{*}$. An additional argument is needed to treat the case when $\beta_{2}u^{e(H)\alpha}-h_{p}(u)$ is maximized at two distinct values. Either by checking the equality conditions in the proof of Theorem 3.1, or by referring to , we know that equality in Corollary 3.2 occurs if and only if $f(x,y)=g(x)g(y)$ for some function $g\colon\to[0,\infty)$. It can then be easily checked that equality in the above sequence of inequalities can only occur when $f$ is a constant function. The value of this constant $u^{*}$ is given by the optimization problem (4.5) and its the uniqueness is addressed in Lemma 4.4.

We now turn to prove Part (b). Since $\beta_{1}\geq\log(d-1)-d/(d-1)$,

By Lemma A.1, $x\mapsto h_{p}(x^{1/d})$ is convex for this value of $p$. Hence, $h_{p}(f)\geq h_{p}(\left\lVert f\right\rVert_{d})$ by Jensen’s inequality with equality if and only if $f$ is a constant function. Since $t(H,f)\leq\left\lVert f\right\rVert_{d}$ by Corollary 3.2,

with equality iff $f$ is the constant function equal to $u^{*}$, the unique maximizer of $\beta_{2}u^{e(H)\alpha}-h_{p}(u)$. The uniqueness of $u^{*}$ follows from Lemma 4.4 together with noting that when $e(H)\alpha>1$ we have $p\geq p_{0}(d)>p_{0}(e(H)\alpha)$ as $d>e(H)\alpha$ and $p_{0}(\cdot)$ is increasing in $[1,\infty)$.

It remains to prove Part (c). We have $0<p<p_{0}(d)$. Let $0<\underline{u}<\overline{u}<1$ be such that the lower common tangent to $x\mapsto h_{p}(x^{1/d})$ touches the curve at $x=\underline{u}^{d}$ and $\overline{u}^{d}$. Since $e(H)\alpha<d$, Lemma A.5 implies that the points $(\underline{u}^{e(H)\alpha},h_{p}(\underline{u}))$ and $(\overline{u}^{e(H)\alpha},h_{p}(\overline{u}))$ both lie on the convex minorant of $x\mapsto h_{p}(x^{1/(e(H)\alpha)}))$ and do not lie on the common lower tangent (if there is one). Let $\underline{\smash{\beta}}_{2}$ and $\overline{\beta}_{2}$ be as in the theorem statement, observing that these are the values of the derivative of $h_{p}(x^{1/(e(H)\alpha)})$ at $x=\underline{u}^{e(H)\alpha}$ and $\overline{u}^{e(H)\alpha}$, respectively. Then for any $\beta\in(\underline{\smash{\beta}}_{2},\overline{\beta}_{2})$, using the slope interpretation of $\beta_{2}$ given in the discussion proceeding this proof, we see that the optimization problem (4.5) is maximized for some $u^{*}\in(\underline{u},\overline{u})$. At the same time, by Lemma 3.4 there exists some $f\in\mathcal{W}_{0}$ such that $t(H,f)>(u^{*})^{e(H)}$ and $h_{p}(f)<h_{p}(u^{*})$. It follows that