1.1. Background and motivation

In this paper we analyse random graphs that are subject to constraints. Statistical physics prescribes which probability distribution on the set of graphs we should choose when we want to model a given type of constraint [Reference Gibbs12]. Two important choices are: (i) the microcanonical ensemble, where the constraints are satisfied by each individual graph; (ii) the canonical ensemble, where the constraints are satisfied as ensemble averages. For random graphs that are large but finite, the two ensembles represent different empirical situations. One of the cornerstones of statistical physics is that the two ensembles become equivalent in the thermodynamic limit, which in our setting corresponds to letting the size of the graph tend to infinity. However, this property does not hold in general. We refer to [Reference Touchette19] for more background on the phenomenon of breaking of ensemble equivalence (BEE).

BEE has been investigated for various choices of constraints, including the degree sequence and the total number of subgraphs of a specific type. The key distinctive object is the relative entropy $S_n$ of the microcanonical ensemble with respect to the canonical ensemble when the graph has n vertices. In the sparse regime, where the number of edges per vertex remains bounded, the relevant quantity is $s_\infty = \lim_{n\to\infty} n^{-1} S_n$ , because n is the scale of the number of vertices. In the dense regime, where the number of edges per vertex is of the order of the number of vertices, the relevant quantity is $s_\infty = \lim_{n\to\infty} n^{-2} S_n$ , because $n^2$ is the scale of the number of edges.

1. Sparse regime: In [Reference Garlaschelli, den Hollander and Roccaverd10, Reference Garlaschelli, den Hollander and Roccaverde11, Reference Squartini, de Mol, den Hollander and Garlaschelli18] it was shown that constraining the degrees of all the vertices leads to BEE, even when the graph consists of multiple communities. An explicit formula was derived for $s_\infty$ in terms of the limit of the empirical degree distribution of the constraint. In [Reference Squartini and Garlaschelli17] a formula was put forward that expresses the specific relative entropy in terms of a covariance matrix under the canonical ensemble.

2. Dense regime: In [Reference Den Hollander, Mandjes, Roccaverde and Starreveld6] it was shown that constraining the densities of a finite number of subgraphs may lead to BEE. The analysis relied on the large deviation principle for graphons associated with the Erdős–Rényi (ER) random graph [Reference Chatterjee3, Reference Chatterjee and Varadhan5]. The main result was a variational formula for $s_\infty$ in the space of graphons. In [Reference Den Hollander, Mandjes, Roccaverde and Starreveld7], for the special case where the constraint is on the densities of the edges and triangles, it was shown that $s_\infty>0$ when the constraints are frustrated, i.e. do not lie on the ER-line where the density of triangles is the third power of the density of edges. Moreover, the asymptotics of $s_\infty$ near the ER-line was identified, and turns out to depend on whether the ER-line is approached from above or below.

It is an open problem whether a single constraint may lead to BEE [Reference Den Hollander, Mandjes, Roccaverde and Starreveld6]. It was believed that this cannot be the case, because for a single constraint there is no frustration. The goal of the present paper is to show that this intuition is wrong: we condition on the density of a given finite simple graph and prove that BEE occurs in a certain range of choices for the density and the number of edges of the simple graph, which we refer to as the BEE-phase. We analyse how $s_\infty$ tends to zero near the curve that borders the BEE-phase. This phase transition is unlike any of the phenomena surrounding BEE observed before. In our case, BEE is due to the coexistence of two densities in the BEE-phase, similar to the phase transition between water and ice. Thus, our paper provides new insight into the mechanisms causing BEE.

In [Reference Dionigi, Garlaschelli, den Hollander and Mandjes9] the gap $\Delta_n$ between the averages of the maximal eigenvalue of the adjacency matrix of a constrained random graph under the two ensembles was considered. A working hypothesis was put forward, stating that BEE is equivalent to this gap not vanishing in the limit as $n\to\infty$ . For a random regular graph with a fixed degree, this equivalence was proved for a range of degrees that interpolates between the sparse and the dense regime. In the present paper we prove the same for the single constraint. In particular, we compute $\delta_\infty = \lim_{n\to\infty} n^{-1} \Delta_n$ , show that $\delta_\infty \neq 0$ if and only if the density and the number of edges of the simple graph fall in the BEE-phase, and analyse how $\delta_\infty$ tends to zero near the curve that borders the BEE-phase.

We will see that the notions of replica symmetry and replica symmetry breaking highlighted in [Reference Lubetzky and Zhao15] play an important role. In the regime of replica symmetry we have a complete identification of $s_\infty$ and $\delta_\infty$ ; in the regime of replica symmetry breaking some pieces of the characterisation are missing. Furthermore, we establish a direct connection between the region of replica symmetry for regular graphs and the region of ensemble equivalence.

1.2. Definitions and preliminaries

In this section, which is partly lifted from [Reference Den Hollander, Mandjes, Roccaverde and Starreveld6], we present the definitions of the main concepts to be used here, together with some key results from prior work. We consider scalar-valued constraints, even though [Reference Den Hollander, Mandjes, Roccaverde and Starreveld6] deals with more general vector-valued constraints.

Section 1.2.1 presents the formal definition of the two ensembles and the definition of ensemble equivalence in the dense regime. Section 1.2.2 recalls some basic facts about graphons. Section 1.2.3 recalls the variational characterisation of ensemble equivalence proven in [Reference Den Hollander, Mandjes, Roccaverde and Starreveld6]. Section 1.2.4 looks at the average of the maximal eigenvalue value of the adjacency matrix in the two ensembles and recalls a working hypothesis put forward in [Reference Dionigi, Garlaschelli, den Hollander and Mandjes9] that links ensemble equivalence to a vanishing gap between the two averages.

1.2.1. Microcanonical ensemble, canonical ensemble, relative entropy

For $n \in \mathbb{N}$ , let $\mathcal{G}_n$ denote the set of all $2^{\binom{n}{2}}$ simple undirected graphs with n vertices. Let T denote a scalar-valued function on $\mathcal{G}_n$ , and $T^*$ a specific scalar that is graphical, i.e. realisable by at least one graph in $\mathcal{G}_n$ . Given $T^*$ , the microcanonical ensemble is the probability distribution $\mathrm{P}_{\mathrm{mic}}$ on $\mathcal{G}_n$ with hard constraint $T^*$ defined, for $G\in \mathcal{G}_n$ , as

\begin{equation*}\mathrm{P}_{\mathrm{mic}}(G) \,{:\!=}\,\left\{\begin{array}{l@{\quad}l}| \{G \in \mathcal{G}_n\colon T(G) = T^* \}|^{-1} \quad & \text{if } T(G) = T^*, \\[3pt] 0 & \text{otherwise}.\end{array}\right. \end{equation*}

The canonical ensemble $\mathrm{P}_{\mathrm{can}}$ is the unique probability distribution on $\mathcal{G}_n$ that maximises the entropy $S_n({\rm P}) \,{:\!=}\, - \sum_{G \in \mathcal{G}_n}{\rm P}(G) \log {\rm P}(G)$ subject to the soft constraint $\langle T \rangle \,{:\!=}\, \sum_{G \in \mathcal{G}_n} T(G)\,{\rm P}(G) = T^*$ . This gives the formula [Reference Jaynes13]

(1.1) \begin{equation} \mathrm{P}_{\mathrm{can}}(G) \,{:\!=}\, \frac{1}{Z(\theta^*)}\,\mathrm{e}^{\theta^*T(G)}, \qquad G \in \mathcal{G}_n,\end{equation}

with $Z(\theta^*)$ the partition function. In (1.1), the Lagrange multiplier $\theta^*$ must be set to the unique value that realises $\langle T \rangle = T^*$ ; see [Reference Den Hollander, Mandjes, Roccaverde and Starreveld6, (2.6) and (2.7)].

The relative entropy of $\mathrm{P}_{\mathrm{mic}}$ with respect to $\mathrm{P}_{\mathrm{can}}$ is defined as

\begin{equation*}S_n(\mathrm{P}_{\mathrm{mic}} \mid \mathrm{P}_{\mathrm{can}})\,{:\!=}\, \sum_{G \in \mathcal{G}_n} \mathrm{P}_{\mathrm{mic}}(G) \log \frac{\mathrm{P}_{\mathrm{mic}}(G)}{\mathrm{P}_{\mathrm{can}}(G)}.\end{equation*}

For any $G_1,G_2\in\mathcal{G}_n$ , $\mathrm{P}_{\mathrm{can}}(G_1)=\mathrm{P}_{\mathrm{can}}(G_2)$ whenever $T(G_1)=T(G_2)$ , i.e. the canonical probability is the same for all graphs with the same value of the constraint. We may therefore rewrite the relative entropy as

\begin{equation*} S_n(\mathrm{P}_{\mathrm{mic}} \mid \mathrm{P}_{\mathrm{can}}) = \log \frac{\mathrm{P}_{\mathrm{mic}}(G^*)}{\mathrm{P}_{\mathrm{can}}(G^*)},\end{equation*}

where $G^*$ is any graph in $\mathcal{G}_n$ such that $T(G^*) =T^*$ .

Remark 1.1. Both the constraint $T^*$ and the Lagrange multiplier $\theta^*$ in general depend on n, i.e. $T^*=T^*_n$ and $\theta^* = \theta^*_n$ . We consider constraints that converge when we pass to the limit $n\to\infty$ , i.e.

(1.2) \begin{equation} \lim_{n\to\infty} T^*_n \,{=\!:}\, T^*_\infty. \end{equation}

Consequently, we expect that

(1.3) \begin{equation} \lim_{n\to\infty} \theta^*_n \,{=\!:}\, \theta^*_\infty. \end{equation}

Throughout the paper we assume that (1.3) holds. If convergence fails, then we may still consider subsequential convergence. The subtleties concerning (1.3) were discussed in detail in [Reference Den Hollander, Mandjes, Roccaverde and Starreveld6, Appendix A].

All the quantities above depend on n. In order not to burden the notation, we exhibit this n-dependence only in the symbols $\mathcal{G}_n$ and $S_n(\mathrm{P}_{\mathrm{mic}} \mid \mathrm{P}_{\mathrm{can}})$ . When we pass to the limit $n\to\infty$ , we need to specify how T(G), $T^*$ , and $\theta^*$ are chosen to depend on n. We refer the reader to [Reference Den Hollander, Mandjes, Roccaverde and Starreveld6], where this issue was discussed in detail.

Definition 1.1. (Ensemble equivalence.) In the dense regime, if

\begin{equation*} s_{\infty} : = \lim_{n\to\infty} n^{-2} S_n(\mathrm{P}_{\mathrm{mic}} \mid \mathrm{P}_{\mathrm{can}})=0, \end{equation*}

then $\mathrm{P}_{\mathrm{mic}}$ and $\mathrm{P}_{\mathrm{can}}$ are said to be equivalent.

This particular notion of ensemble equivalence is known as measure equivalence of ensembles and is standard in the study of ensemble equivalence of networks. Other notions of ensemble equivalence are thermodynamic equivalence and macrostate equivalence. Under certain hypotheses, the three notions have been shown to be equivalent for physical systems [Reference Touchette19]. We refer the reader to [Reference Touchette19, Reference Touchette, Ellis and Turkington20] for further discussion of different notions of ensemble equivalence.

1.2.2. Graphons

There is a natural way to embed a simple graph on n vertices in a space of functions called graphons. Let $\mathcal{W}$ be the space of functions $h\colon[0,1]^2 \to [0,1]$ such that $h(x,y) = h(y,x)$ for all $(x,y) \in [0,1]^2$ . A finite simple graph G on n vertices can be represented as a graphon $h^{G} \in \mathcal{W}$ in a natural way as

(1.4) \begin{equation} h^{G}(x,y) \,{:\!=}\, \left\{ \begin{array}{l@{\quad}l} 1 \quad &\mbox{if there is an edge between vertex } \lceil{nx}\rceil \mbox{ and vertex } \lceil{ny}\rceil,\\[3pt] 0 &\mbox{otherwise}. \end{array} \right.\end{equation}

The space of graphons $\mathcal{W}$ is endowed with the cut distance

\begin{equation*}d_{\square} (h_1,h_2) \,{:\!=}\, \sup_{S,T\subset [0,1]}\bigg|\int_{S\times T} \text{d} x\,\text{d} y\,[h_1(x,y) - h_2(x,y)]\bigg|,\qquad h_1,h_2 \in \mathcal{W}.\end{equation*}

On $\mathcal{W}$ there is a natural equivalence relation $\sim$ . Let $\Sigma$ be the space of measure-preserving bijections $\sigma\colon [0,1] \to [0,1]$ . Then $h_1(x,y)\sim h_2(x,y)$ if $\delta_{\square}(h_1,h_2)=0$ , where $\delta_{\square}$ is the cut metric defined by

\begin{equation*} \delta_{\square}(\tilde{h}_1,\tilde{h}_2) \,{:\!=}\, \inf _{\sigma_1,\sigma_2 \in \Sigma} d_{\square}(h_1^{\sigma_1}, h_2^{\sigma_2}), \qquad \tilde{h}_1,\tilde{h}_2 \in \tilde{\mathcal{W}},\end{equation*}

with $h^\sigma(x,y)=h(\sigma x,\sigma y)$ . This equivalence relation yields the quotient space $(\tilde{\mathcal{W}},\delta_{\square})$ . As noted above, we suppress the n-dependence. Thus, by G we denote any simple graph on n vertices, by $h^G$ its image in the graphon space $\mathcal{W}$ , and by $\tilde{h}^G$ its image in the quotient space $\tilde{\mathcal{W}}$ . For a more detailed description of the structure of the space $(\tilde{\mathcal{W}},\delta_{\square})$ we refer to [Reference Borgs, Chayes, Lovász, Sós and Vesztergombi1, Reference Borgs, Chayes, Lovász, Sós and Vesztergombi2, Reference Diao, Guillot, Khare and Rajaratnam8].

For $h \in \tilde{\mathcal{W}}$ and F a finite simple graph with m vertices and edge set E(F), define

\begin{equation*} t(F,h) \,{:\!=}\, \int_{[0,1]^m} \prod_{\{i,j\} \in E(F)} h(x_i,x_j) \,\mathrm{d}x_1\ldots\,\mathrm{d}x_m.\end{equation*}

Then the homomorphism density of F in G equals $t(F,h^G)$ , where $h^G$ is the empirical graphon defined in (1.4).

In this paper we focus on the special case where the constraint $T(G)=T(h^G)\,{:\!=}\,t(F,h^G)$ is on the homomorphism density $T^*_n$ of a specific subgraph F. The map T is well-defined on both the space of graphs $\mathcal{G}_n$ for each n and the space of graphons. Rewriting (1.1), we obtain

\begin{equation*} \mathrm{P}_{\mathrm{can}}(G) = \mathrm{e}^{n^2[\theta_n^* T(G)-\psi_n(\theta_n^*)]}, \qquad G \in \mathcal{G}_n,\end{equation*}

where

\begin{equation*} \psi_n(\theta_n^*) \,{:\!=}\, \frac{1}{n^2}\log\sum_{G\in\mathcal{G}_n} \mathrm{e}^{n^2 [\theta_n^* T(G)]} = \frac{1}{n^2}\log Z(\theta_n^*).\end{equation*}

It turns out that, under the scaling $n^2$ , the function $\psi_n$ converges. Hence, rewriting (1.1) in this form aids us in the analysis of the canonical ensemble.

1.2.3. Variational characterisation of ensemble equivalence

In order to characterise the asymptotic behaviour of the two ensembles, the entropy function of a Bernoulli random variable is essential. For $u\in [0,1]$ , let

\begin{equation*}I(u) \,{:\!=}\, \tfrac{1}{2}u\log u +\tfrac{1}{2}(1-u)\log(1-u).\end{equation*}

Extend the domain of this function to the graphon space $\mathcal{W}$ by defining

\begin{equation*} I(h) \,{:\!=}\, \int_{[0,1]^2} \text{d} x\, \text{d} y\,I(h(x,y))\end{equation*}

(with the convention that $0\log0\,{:\!=}\,0$ ). On the quotient space $(\tilde{\mathcal{W}},\delta_{\square})$ , define $I(\tilde{h}) = I(h)$ , where h is any element of the equivalence class $\tilde{h}$ . Note that I(h) takes values in $\big[{-}\tfrac12\log 2,0\big]$ . Apart from a shift by $\tfrac12\log 2$ , $h \mapsto I(h)$ plays the role of the rate function in the large deviation principle for the empirical graphon associated with the Erdős–Rényi random graph, derived in [Reference Chatterjee and Varadhan5].

The key result in [Reference Den Hollander, Mandjes, Roccaverde and Starreveld6] is the following variational formula for $s_\infty$ , where $\tilde{\mathcal{W}}^* \,{:\!=}\, \{\tilde{h}\in \tilde{\mathcal{W}}\colon T(h) = T^*_\infty\}$ is the subspace of all graphons that meet the constraint $T^*_\infty$ . This is a compact set, since T is continuous in the cut metric and $(\tilde{\mathcal{W}},\delta_{\square})$ is compact [Reference Lovász and Szegedy14].

Theorem 1.1. (Variational characterisation of ensemble equivalence.) Subject to (1.2) and (1.3), $\lim_{n\to\infty} n^{-2} S_n(\mathrm{P}_{\mathrm{mic}} \mid \mathrm{P}_{\mathrm{can}}) \,{=\!:}\, s_\infty$ , with

(1.5) \begin{equation} s_\infty = \sup_{\tilde{h}\in \tilde{\mathcal{W}}} \big[\theta^*_\infty T(\tilde{h})-I(\tilde{h})\big] -\sup_{\tilde{h}\in \tilde{\mathcal{W}}^*} \big[\theta^*_\infty T(\tilde{h}) - I(\tilde{h})\big]. \end{equation}

Theorem 1.1 and the compactness of $\tilde{\mathcal{W}}^*$ give us a variational characterisation of ensemble equivalence: $s_\infty = 0$ if and only if at least one of the maximisers of $\theta^*_\infty T(\tilde{h})-I(\tilde{h})$ in $\tilde{\mathcal{W}}$ also lies in $\tilde{\mathcal{W}}^* \subset \tilde{\mathcal{W}}$ , i.e. satisfies the hard constraint.

We need the following lemma, which relates $T_\infty^*$ and $\theta_\infty^*$ without requiring knowledge of $T_n^*$ and $\theta_n^*$ .

Lemma 1.1. Under the assumptions in (1.2) and (1.3), $\theta_\infty^* = \arg\max_{\theta \in \mathbb{R}} [\theta T_\infty^*-\psi_\infty(\theta)]$ , where $\psi_\infty(\theta)\,{:\!=}\,\lim_{n\to\infty}\psi_n(\theta)=\sup_{\tilde{h}\in\tilde{\mathcal{W}}}\big[\theta T(\tilde{h})-I(\tilde{h})\big]$ .

Proof. For every $n \in \mathbb{N}$ ,

\begin{equation*} \theta_n^* = \arg\max_{\theta \in \mathbb{R}} [n^2 [\theta T_n^*-\psi_n(\theta)]] = \arg\max_{\theta \in \mathbb{R}} [\theta T_n^*-\psi_n(\theta)]. \end{equation*}

Let $f_n(\theta,T_n^*) \,{:\!=}\, \theta T^*_n - \psi_n(\theta)$ and $f_\infty(\theta,T_\infty^*) = \theta T^*_\infty-\psi_\infty(\theta)$ . By [Reference Den Hollander, Mandjes, Roccaverde and Starreveld6, Theorem 3.2 and Lemma A.1],

\begin{align*} f_n(\theta_n^*,T_n^*) & = \sup_{\theta\in\mathbb{R}} f_n(\theta,T_n^*) = [\theta_n^* T_n^*-\psi_n(\theta_n^*)] \to [\theta_\infty^*T_\infty^* - \psi_\infty(\theta^*_\infty)] \\[3pt] & = \theta_\infty^* T_\infty^* - \sup_{\tilde{h}\in\tilde{\mathcal{W}}} \big[\theta_\infty^* T(\tilde{h})-I(\tilde{h})\big] = f_\infty(\theta_\infty^*,T_\infty^*), \qquad n \to \infty. \end{align*}

Furthermore, for every $\theta \in \mathbb{R}$ , $f_n(\theta,T_n^*) \leq f_n(\theta_n^*,T_n^*)$ , and hence

\begin{equation*} f_\infty(\theta,T_\infty^*) = \lim_{n\to\infty} f_n(\theta,T_n^*) \leq \lim_{n\to\infty} f_n(\theta_n^*,T_n^*) = f_\infty(\theta_\infty^*,T_\infty^*), \end{equation*}

so that $\theta_\infty^*$ is a maximiser of $f_\infty(\cdot,T_\infty^*)$ .

1.2.4. Maximal eigenvalue of the adjacency matrix

In [Reference Dionigi, Garlaschelli, den Hollander and Mandjes9] a working hypothesis was put forward, stating that breaking of ensemble equivalence is manifested by a gap between the scaling limits of the averages of the maximal eigenvalue of the adjacency matrix of the random graph under the two ensembles. More precisely, let $\lambda_n$ denote the maximal eigenvalue of the adjacency matrix of $G \in \mathcal{G}_n$ . Then the working hypothesis is that

\begin{align*} \lim_{n\to\infty} \Delta_n \neq 0 & \ \Longrightarrow \mathrm{BEE}, \\[3pt] \mathrm{BEE} & \ \Longrightarrow \lim_{n\to\infty} \Delta_n \neq 0 \text{ apart from exceptional constraints},\end{align*}

with $\Delta_n \,{:\!=}\, \mathrm{E}_{\mathrm{can}}[\lambda_n] - \mathrm{E}_{\mathrm{mic}}[\lambda_n]$ . In [Reference Dionigi, Garlaschelli, den Hollander and Mandjes9] this equivalence was proven for the specific example where the constraint is on all the degrees being equal to d(n), with $(\log n)^\beta \leq d(n) \leq n - (\!\log n)^\beta$ for some $\beta \in (6,\infty)$ . It turns out that BEE occurs and that $\lim_{n\to\infty} \Delta_n = 1-p$ when $\lim_{n\to\infty} n^{-1} d(n)=p \in [0,1]$ , i.e. the exceptional constraints correspond to the ultra-dense regime where $p=1$ .

For our single constraint in the dense regime, we will be interested in the quantity $\delta_\infty \,{:\!=}\, \lim_{n\to\infty} n^{-1} \Delta_n$ .

1.3. Main results

In what follows, F is any finite simple graph with k edges, and the constraint is on the homomorphism density of F being equal to $T^*_n$ , as defined in Section 1.2.2. Recall from Remark 1.1 that we assume that $(T^*_n)_{n\in\mathbb{N}}$ and $(\theta_n)_{n\in\mathbb{N}}$ converge to some constants $T_{\infty}^*$ and $\theta_{\infty}^*$ respectively. For the sake of convenience, we write $T^*=T^*_\infty$ and $\theta^*=\theta_\infty^*$ . In the four theorems below we allow for $k \in [1,\infty)$ , although $k\in\mathbb{N}$ is needed to interpret the constraint in terms of a subgraph density.

1.3.1. Parameter regime

Our first two theorems identify the parameter regime for BEE.

Theorem 1.2. (Computational criterion for ensemble equivalence.) For $\theta \in [0,\infty)$ and $k \in [1,\infty)$ , let $u^*(\theta,k)$ be a maximiser of

(1.6) \begin{equation} \sup_{u \in [0,1]} [\theta u^k-I(u)]. \end{equation}

1. (a) For every $T^* \in \big[\big(\tfrac12\big)^k,1\big)$ there is ensemble equivalence if and only if there exists a $\theta_0 = \theta_0(T^*,k) \in [0,\infty)$ such that $(u^*(\theta_0,k))^k = T^*$ . In that case the Lagrange multiplier $\theta^*=\theta^*(T^*,k)$ equals $\theta_0$ .

2. (b) There exists a unique $\hat{\theta} = \hat{\theta}(k) \in [0,\infty)$ such that $\theta^*(T^*,k) = \hat{\theta}$ for all $T^*$ for which there is breaking of ensemble equivalence.

Theorem 1.3. (Phase diagram.)

1. (a) There exists a function $k_\mathrm{c} \colon (0,1) \to [1,\infty)$ such that for every $T^*\in(0,1)$ there is ensemble equivalence when $\log_2(1/T^*) \leq k \leq k_\mathrm{c}(T^*)$ and breaking of ensemble equivalence when $k>k_\mathrm{c}(T^*)$ .

2. (b) $T^* \mapsto k_\mathrm{c}(T^*)$ achieves a unique minimum at the point $(T_0,k_0)$ , with $k_0$ the unique solution of the equation $(({k_0-1})/{k_0}) \log(k_0-1) = 1$ and $T_0 = (({k_0-1})/{k_0})^{k_0}$ .

3. (c) $T^* \mapsto k_\mathrm{c}(T^*)$ is analytic on $(0,1) \setminus \{T_0\}$ .

4. (d) $\big(\frac{1}{2}\big)^{k_\mathrm{c}(T^*)} \sim T^*$ as $T^* \downarrow 0$ and $k_\mathrm{c}(T^*)\big(\frac{1}{2}\big)^{k_\mathrm{c}(T^*)} \sim 1-T^*$ as $T^* \uparrow 1$ .

A numerical picture of the phase diagram described in Theorem 1.3 is shown in Fig. 1.

Figure 1.

A numerical picture of the phase diagram. The left and right lines together form the critical curve $(T^*,k_\mathrm{c}(T^*))$ . In the figure, $T^*$ is denoted by T ^* and $k_\mathrm{c}(T^*)$ is denoted by k(T ^*). The minimum is achieved at $k_0 = 4.591\ldots$ and $T_0 = 0.3237\ldots$

Note that the results above only hold in the regime $T^* \in \big[\big(\tfrac12\big)^k,1\big)$ , which corresponds to the regime $\theta^*\geq0$ . This assumption is necessary, since the results from [Reference Chatterjee and Diaconis4] that we use only hold for non-negative $\theta^*$ . For k and $T^*$ not in this regime, we do not know if there is ensemble equivalence.

1.3.2. Replica symmetry

Our last two theorems quantify the specific relative entropy and the spectral gap in the replica symmetry regime. This regime was first defined in [Reference Chatterjee and Varadhan5] and further studied in [Reference Lubetzky and Zhao15]. Using the theory developed in [Reference Lubetzky and Zhao15], it is possible to quantify the specific relative entropy $s_\infty$ and the difference of the largest eigenvalue $\delta_\infty$ for certain $T^*$ in the BEE-phase.

Definition 1.2. (Replica symmetry.) Consider the Erdős–Rényi random graph G on n vertices with retention probability $p \in [0,1]$ conditioned on $t(F,G)\geq T^*$ for some finite simple graph F. If G converges in the cut metric to a constant graphon, then we say that $T^*$ is in the replica symmetric region.

From the theory of large deviations for random graphs developed in [Reference Chatterjee and Varadhan5], we know that $T^*$ is in the replica symmetric region if and only if

(1.7) \begin{equation} \inf_{t(F,f)\geq T^*}I_p(f)\end{equation}

is minimised by a constant graphon, with $I_p$ the rate function given by

(1.8) \begin{equation} I_p(f) = \int_{[0,1]^2}\,\mathrm{d}x\,\mathrm{d}y\bigg(f(x,y)\log\frac{f(x,y)}{p}+[1-f(x,y)]\log\frac{1-f(x,y)}{1-p}\bigg).\end{equation}

Note that $I(f) = I_{{1}/{2}}(f)-\frac{1}{2}\log2$ . Hence, if $T^*$ is in the replica symmetric region, then there is an explicit solution for the second supremum in (1.5). In [Reference Lubetzky and Zhao15], it was shown that $T^*$ is in the replica symmetric region when $(T^*,I_p(T^{*\,1/d}))$ lies on the convex minorant of the function $x\mapsto I_p(x^{1/d})$ , with d the maximum degree of the subgraph F. If F is regular, then the converse statement holds as well.

Fix a subgraph F with k edges and maximum degree d. Let $T_1^*(k) \in \big(\big(\tfrac12\big)^k,T_0\big)$ and $T_2^*(k) \in (T_0,1)$ be the two solutions of the equation $k_\mathrm{c}(T^*(k)) = k$ , so that $(T_1^*(k),T_2^*(k)) = \text{BEE-phase}$ . In Lemma 3.1, we prove that the replica symmetric region contains $\big[\big(\frac{1}{2}\big)^k,T_1^*(d)\big] \cup [T_2^*(d),1]$ . Thus, if $d<k$ , then in part of the BEE-phase there is replica symmetry. This allows us to formulate the following two theorems (which are vacuous for $d=k$ ).

Theorem 1.4. (Specific relative entropy.) For every $T^*$ in the replica symmetric part of the phase of breaking of ensemble equivalence,

\begin{equation*} s_\infty = \left\{ \begin{array}{l@{\quad}l} \hat{\theta}(k)[T_1^*(k)-T^*] + \big[I(T^{*\,1/k})-I(T_1^*(k)^{1/k})\big] > 0,\quad & T^* \in (T_1^*(k),T_1^*(d)], \\[4pt] \hat{\theta}(k)[T_2^*(k)-T^*] + \big[I(T^{*\,1/k})-I(T_2^*(k)^{1/k})\big] > 0, & T^* \in [T_2^*(d),T_2^*(k)). \end{array} \right. \end{equation*}

Consequently,

\begin{equation*} s_\infty = \left\{ \begin{array}{l@{\quad}l} C(T_1^*(k),k)\,[T^*-T_1^*(k)]^2 + O([T-T_1^*(k)]^3), \quad & T^* \downarrow T_1^*(k), \\[4pt] C(T_2^*(k),k)\,[T^*-T_2^*(k)]^2 + O([T-T_2^*(k)]^3), & T^* \uparrow T_2^*(k), \end{array} \right. \end{equation*}

with

\begin{equation*} C(T^*,k) = \frac{T^{*\,(1-2k)/k}}{2k}\bigg\{ \frac{1}{k}\bigg(1+\frac{T^{*\,1/k}}{1-T^{*\,1/k}}\bigg) + \bigg(\frac{1}{k}-1\bigg)\log\bigg(\frac{T^{*\,1/k}}{1-T^{*\,1/k}}\bigg)\bigg\}. \end{equation*}

Theorem 1.5. (Spectral signature.) For every $T^*$ in the replica symmetric part of the phase of breaking of ensemble equivalence,

\begin{align*} \delta_\infty & = \frac{T^{*\,1/k}_1[T^*_2(k)-T^*] + T^{*\,1/k}_2[T^*-T^*_1(k)]} {T^*_2(k)-T^*_1(k)}-T^{*\,1/k}<0, \\[3pt] T^* & \in (T^*_1(k),T^*_1(d)] \cup [T^*_2(d),T^*_2(k)). \end{align*}

Consequently,

\begin{equation*} \delta_\infty = \left\{ \begin{array}{l@{\quad}l} \hat{C}(T^*_1(k),k)[T^*-T^*_1(k)] + O([T^*-T^*_1(k)]^2), & T^*\downarrow T^*_1(k), \\[3pt] \hat{C}(T^*_2(k),k)[T^*-T^*_2(k)] + O([T^*-T^*_2(k)]^2), & T^*\uparrow T^*_2(k), \end{array} \right. \end{equation*}

with

\begin{equation*} \hat{C}(T^*,k) = \frac{T^{*\,1/k}_2(k)-T^{*\,1/k}_1(k)}{T^*_2(k)-T^*_1(k)}-\frac{1}{k} T^{*\,(1-k)/k}. \end{equation*}

1.4. Typical graph under the microcanonical and canonical ensemble

The BEE-phase can also be characterised through convergence of the random graph drawn from the two ensembles. In Lemmas 5.1 and 5.2 we show that the random graph drawn from the canonical ensemble converges to the maximiser(s) of the first supremum of (1.5), while the random graph drawn from the microcanonical ensemble converges to the maximiser(s) of the second supremum of (1.5).

Outside the BEE-phase, both suprema are attained by the constant graphon $h\equiv T^{*\,1/k}$ , meaning that for large n both ensembles behave approximately like the Erdős–Rènyi random graph with retention probability $p=T^{*\,1/k}$ . Inside the BEE-phase, the first supremum is maximised by the two constant graphons $T_1^*(k)^{1/k}$ and $T_2^*(k)^{1/k}$ , neither of which lies in $\tilde{\mathcal{W}}^*$ . Consequently, the random graph drawn from the canonical ensemble converges to the random graphon

\begin{equation*} \frac{T_2^*(k)-T^*}{T_2^*(k)-T_1^*(k)}\delta_{T_1^*(k)^{1/k}} + \frac{T^*-T_1^*(k)}{T_2^*(k)-T_1^*(k)}\delta_{T_2^*(k)^{1/k}},\end{equation*}

meaning that for large n the canonical ensemble behaves approximately like a mixture of two Erdős–Rényi random graphs. If $T^*$ is in the replica symmetric part of the BEE-phase, then the second supremum is still minimised by the constant graphon $h \equiv T^{*\,1/k}$ . Hence, the random graph is asymptotically deterministic under the microcanonical ensemble and random under the canonical ensemble. Thus, BEE occurs due to coexistence of two densities. This is similar in spirit to the coexistence of water and ice at the melting point, at which a first-order phase transition between water and ice occurs.

In the region of replica symmetry breaking, the maximisers of the second supremum are unknown, and it is not even known whether or not there is a unique maximiser (see Fig. 2). In the case of non-uniqueness, also under the microcanonical ensemble the random graph is asymptotically random.

Figure 2.

A numerical picture of the average largest eigenvalue $\lambda=\lim_{n\to\infty}\frac{1}{n}\mathbb{E}[\lambda_n]$ of the adjacency matrix under the microcanonical ensemble (top curve) and the canonical ensemble (bottom curve), as a function of $T^*$ for a subgraph F with $k=7$ edges and maximum degree $d=5$ . The top curve is shown only for $T^*$ in the replica symmetric region. In the region of replica symmetry breaking we have no explicit expression for $\lambda$ under the microcanonical ensemble.

1.5. Discussion and outline

Theorem 1.2 reduces the variational formula on $\tilde{\mathcal{W}}$ to a variational formula on [0, 1], and is an application of a reduction principle explained in [Reference Chatterjee and Diaconis4] (see also [Reference Chatterjee3]). The proof relies on the variational characterisation in Theorem 1.1. The main difficulty lies in computing the tuning parameter $\theta^*$ as a function of the density $T^*$ , which is resolved through Lemma 1.1. The proof follows from an analysis of the two variational expressions, for which we rely in part on the results in [Reference Radin and Yin16]. From Theorem 1.2, for each k we can identify the BEE-phase as follows. The expression in (1.6) has at most two local maximisers $u_1^*(\theta)<u_2^*(\theta)$ , which are both increasing in $\theta$ . For $\theta<\hat{\theta}$ , $u_1^*(\theta)$ is the global maximiser; for $\theta>\hat{\theta}$ , $u_2^*(\theta)$ is the global maximiser; and for $\theta=\hat{\theta}$ , $u_1^*(\theta)$ and $u_2^*(\theta)$ are both global maximisers. Hence, the values $u\in(u_1^*(\theta),u_2^*(\theta))$ can never be a global maximiser, and so the BEE-phase contains $(u_1^*(\theta)^k,u_2^*(\theta)^k)$ . Since $u_1^*(0)=\frac{1}{2}$ and $\lim_{\theta\rightarrow\infty}u_2^*(\theta)=1$ , the interval $(u_1^*(\theta)^k,u_2^*(\theta)^k)$ is the entire BEE-phase.

Theorem 1.3 identifies the BEE-phase and captures the main properties of the critical curve bordering this phase. The proof relies on Lemma 3.1, which allows us to use results from [Reference Lubetzky and Zhao15] and establish a connection between ensemble equivalence and replica symmetry, in the sense that $T^*$ lies in the BEE-phase for a subgraph with k edges if and only if $T^*$ lies in the region of replica symmetry breaking for $p=\frac12$ and a k-regular subgraph (recall (1.7) and (1.8)). This connection is purely analytic: it establishes equivalence of variational formulas and implies that the graph in Fig. 1 is a cross-section of the curves in [Reference Lubetzky and Zhao15, Figure 2] at $p=\frac12$ . It is not clear, however, how to probabilistically interpret the relationship between replica symmetry for regular subgraphs and breaking of ensemble equivalence for general graphs. Note that we do not require any regularity of the subgraph F, and also the degrees of F do not play any role. It might be easier to use the variational formula in (1.6) (with $I_p$ instead of I) to analyse replica symmetry, rather than the convex minorant of $ x \mapsto I_p(x^{1/k})$ .

Theorem 1.4 gives an explicit formula for the specific relative entropy $s_\infty$ in part of the BEE-phase. The proof exploits the connection with replica symmetry. If a subgraph has more edges than its maximal degree (i.e. is not a k-star), then the BEE-phase near $T_1^*(k)$ and $T_2^*(k)$ is replica symmetric. This implies that the second supremum in (1.5) also has a constant maximiser, which allows us to explicitly compute $s_\infty$ . It turns out that the relative entropy undergoes a second-order phase transition as $T^*$ approaches the critical curve.

Theorem 1.5 shows that the working hypothesis put forward in [Reference Dionigi, Garlaschelli, den Hollander and Mandjes9] is met in the replica symmetric part of the BEE-phase. A random graph drawn from the canonical ensemble converges to a constant graphon whose height is a random mixture of the two maximisers $u_1,u_2$ of (1.6). The average largest eigenvalue converges to a value on the line segment connecting $(u_1^{1/k},u_1)$ and $(u_2^{1/k},u_2)$ . In the region of replica symmetry, a random graph drawn from the microcanonical ensemble converges to the constant graphon whose height is $(T^*)^{1/k}$ , as illustrated in Fig. 2. Note that the average largest eigenvalue is larger in the microcanonical ensemble than in the canonical ensemble, contrary to what was found in [Reference Dionigi, Garlaschelli, den Hollander and Mandjes9], where the constraint was on the degree sequence. It turns out that $\delta_\infty$ undergoes a first-order phase transition as $T^*$ approaches the critical curve.

The numerical picture of the phase diagram in Fig. 1 was made using Mathematica. The computations involve finding an approximate value of $\hat{\theta}(k)$ for each k (up to an accuracy of five digits), and computing $u_1^*(\hat{\theta}(k),k)$ and $u_2^*(\hat{\theta}(k),k)$ . The dotted lines are formed by the points $(u_1^*(k)^k,k)$ and $(u_2^*(k)^k,k)$ . This is done for k starting at 4.592 and increasing with increments of 0.002.

In [Reference Touchette19], BEE for interacting particle systems was studied at three different levels: thermodynamic, macrostate, and measure. It was shown that these levels are in fact equivalent. A general formalism was put forward, based on an abstract large deviation principle, linking the occurrence of BEE to non-convexity of the rate function associated with the microcanonical ensemble as a function of the parameters controlling the constraint. In our context, the large deviation principle for graphons in [Reference Chatterjee and Varadhan5] provides the conceptual basis for identifying the BEE-phase via the variational formula derived in [Reference Den Hollander, Mandjes, Roccaverde and Starreveld6], and the link with the convex minorant mentioned above fits in with the picture provided in [Reference Touchette19].

Theorems 1.2–1.5 are proved in Sections 2–5, respectively.