Maximum independent sets on random regular graphs

Introduction

An independent set in a graph is a subset of the vertices of which no two are neighbors. Establishing asymptotics of the maximum size of an independent set (the independence number) on random graphs is a classical problem in probabilistic combinatorics. On the random $d$-regular graph $\smash{\mathcal{G}_{n,d}}$, the independence number grows linearly in the number $n$ of vertices. Upper bounds were established by Bollobás and McKay , and lower bounds by Frieze–Suen , Frieze–Łuczak and Wormald , using a combination of techniques, including first and second moment bounds, differential equations, and switchings. The bounds are quite close, with the maximal density of occupied vertices (the independence ratio) roughly asymptotic to $2(\log d)/d$ in the limit of large $d$ — however, for every fixed $d$ there remains a constant-size gap in the bounds on the independence ratio. For a more complete history and discussion of many related topics see the survey of Wormald .

In fact, a long-standing open problem (see ) was to determine if there even exists a limiting independence ratio. A standard martingale bound implies that the independence number has $O(n^{1/2})$ fluctuations about its mean, so an equivalent question was to prove convergence of the expected independence ratio. This conjecture was recently resolved by Bayati–Gamarnik–Tetali using interpolation methods from statistical physics. Their method is based on a sub-additivity argument which does not yield information on the limiting independence ratio or the order of fluctuations.

In this paper, we establish for all sufficiently large $d$ the asymptotic independence ratio $\alpha_{\star}=\lim_{n}\bm{A}_{n}/n$, and determine also the lower-order logarithmic correction. Further, we prove tightness of the non-normalized independence number, proving that the random variable is much more strongly concentrated than suggested by the classical $O(n^{1/2})$ bound:

The maximum size $\bm{A}_{n}$ of an independent set in the random $d$-regular graph $\smash{\mathcal{G}_{n,d}}$ has constant fluctuations about

for $\alpha_{\star}$ and $c_{\star}$ explicit functions of $d$, provided $d$ exceeds an absolute constant $d_{0}$.

The values $\alpha_{\star}$ and $c_{\star}$ are given in terms of a function ${}^{\star}\bm{\Phi}\equiv{}^{\star}\bm{\Phi}_{d}$ defined on the interval $(5/3)(\log d)/d\leq\alpha\leq 2(\log d)/d$: the function is smoothly decreasing with a unique zero $\alpha_{\star}$, and we set $c_{\star}\equiv-[2\cdot{}^{\star}\bm{\Phi}^{\prime}(\alpha_{\star})]^{-1}$ (positive since the function is decreasing). Explicitly,

where $q$ is determined from $\alpha$ by solving the equation

and $\lambda=q[1-(1-q)^{d-1}]/(1-q)^{d}$. For $\lambda$ determined from $\alpha$ in this manner we will see that ${}^{\star}\bm{\Phi}^{\prime}(\alpha)=-\log\lambda$, therefore $c_{\star}=[2\log\lambda_{\star}]^{-1}$ for $\lambda_{\star}$ corresponding to $\alpha_{\star}$.

A natural question is whether the same behavior holds for regular graphs of low degree. Though it is certainly possible to determine an explicit $d_{0}$ from our proof, we have not done so because the calculations in the paper are already daunting, and have not been carried out with a view towards optimizing $d_{0}$. More importantly, our result is in line with the one-step replica symmetry breaking (1rsb) prediction, which is believed to fail on low-degree graphs where physicists expect full replica symmetry breaking . In the latter regime no formula is predicted even at a heuristic level.

Ideas from statistical physics have greatly advanced our understanding of random constraint satisfaction and combinatorial optimization problems . This deep, but for the most part non-rigorous, theory has led to a detailed picture of the geometry of the space of solutions for a broad class of such problems, including exact predictions for their satisfiability threshold. While some aspects of this rich picture have been established, including celebrated results such as Aldous’s solution to the random assignment problem and Talagrand’s proof of Parisi’s formula for the Sherrington–Kirkpatrick spin-glass model , many of the most important ideas remain at the level of conjecture. We believe that recent developments, including our own previous work , make it possible to establish thresholds predicted by this theory for many such models.

The natural approach to studying the independence ratio is the (first and second) moment method applied to the number of $Z_{n\alpha}$ of independent sets of fixed density $\alpha$. Indeed, an analogous approach correctly determines the asymptotic independence number for the dense Erdős-Rényi random graph . On sparse random graph ensembles, however, the second moment approach fails to locate the sharp transition. Due to the sparsity of the graph, almost every independent set can be locally perturbed in a linear number of places: thus the existence of a single independent set implies the existence of a cluster of exponentially many independent sets, all related by sequences of local perturbations. Moreover the expected cluster size remains exponentially large even beyond the first moment threshold — thus there is a regime below the first moment threshold where it overcomes the first moment, causing the second moment to be exponentially large compared with the first moment squared.

From statistical physics, the (mostly heuristic) understanding of this phenomenon is that as $\alpha$ exceeds roughly $(\log d)/d$, the solution space of independent sets becomes shattered into exponentially many well-separated clusters . This geometry persists up to a further (conjectured) structural transition where the solution space condensates onto the largest clusters. In the non-trivial regime between the condensation and satisfiability transitions, most independent sets are concentrated within a bounded number of clusters according to the theory from statistical physics. This within-cluster correlation then dominates the moment calculation, causing the failure of the second moment method.

In this paper, we determine the exact threshold by a novel approach which rigorizes the 1rsb heuristic from statistical physics, which suggests that we count clusters of independent sets rather than the sets themselves. Our proof has several new ideas which we now describe.

Secondly, we note that this new model is itself a Gibbs measure on a random hypergraph, and its properties of local rigidity hint that applying the second moment in this model does locate the exact threshold. However, the actual moment calculation appears at first intractable, involving maximizations over high-dimensional simplices. By a certain “Bethe variational principle” we are able to characterize local maximizers via fixed points of certain tree recursions, reducing the optimization to (in the second moment) $81$ real variables. With delicate a priori estimates we are able to establish symmetry relations among these variables which drastically reduce the dimensionality and allows us finally to pinpoint the global maximizers.

The second moment method itself only establishes the existence of clusters with asymptotically positive probability. Our final innovation is a method to improve positive probability bounds to high probability, which in this model yields the constant fluctuations. The approach is based on controlling the incremental fluctuations of the Doob martingale of a certain log-transform of the partition function.

As an illustration of the robustness of these methods, in a companion paper we apply the same techniques to establish the exact satisfiability threshold for the random regular not-all-equal-sat problem. This gives the first threshold for a sparse constraint satisfaction model with replica symmetry breaking. We expect ultimately that these methods may be extended to other combinatorial properties such as the chromatic number or maximum cut, and to the sparse Erdős-Rényi random graphs.

2. Notation

We work with the $d$-regular configuration model: a $d$-regular graph with vertex set $[n]\equiv\{1,\ldots,n\}$ is a perfect matching on the set $[nd]$ of labelled half-edges, where half-edge $i$ is incident to vertex $\lceil i/d\rceil$. Assume $nd$ is even; the number of $d$-regular graphs on $[n]$ is the double factorial

Under the configuration model, the random $d$-regular graph $\smash{\mathcal{G}_{n,d}}$ corresponds to the uniformly random perfect matching on $[nd]$.

Acknowledgements

We are grateful to Sourav Chatterjee, Amir Dembo, Persi Diaconis, Elchanan Mossel, and Andrea Montanari for helpful conversations.

Independent sets and coarsening algorithm

Let $Z_{n\alpha}$ count the number of independent sets of cardinality $n\alpha$ on graph $G$.

The expected number of independent sets of size $n\alpha$ on $\smash{\mathcal{G}_{n,d}}$ is

where $(A)_{b}$ and $[A]_{b}$ denote respectively the falling factorial and falling double factorial:

It is straightforward to check that $\Phi^{\prime}(\alpha)>0$ for small $\alpha$ and $\Phi^{\prime\prime}(\alpha)<0$ for all $\alpha<\mathchoice{\tfrac{1}{2}}{\smash{\tfrac{1}{2}}}{\tfrac{1}{2}}{\tfrac{1}{2}}$, so $\Phi$ has a unique zero-crossing $\alpha_{\square}$. The function $F$ is decreasing in $\alpha$ with unique zero

where $W$ denotes the principal branch of the Lambert $W$ function defined by $z=W(z)e^{W(z)}$ (see and references therein). Near $z=\infty$, the function $W$ has absolutely convergent series expansion

where $[\smash{\begin{smallmatrix}n\vskip 0.0pt\\ m\end{smallmatrix}}]$ are the Stirling cycle numbers (or unsigned Stirling numbers of the first kind), generated by $\log(1+z)^{m}=m!\sum_{n\geq 0}(-1)^{n+m}[\smash{\begin{smallmatrix}n\vskip 0.0pt\\ m\end{smallmatrix}}]z^{n}/n!$. By estimating $F^{\prime}$ and $F^{\prime\prime}$ near $\widetilde{\alpha}_{\square}$ we see that $\alpha_{\square}=\widetilde{\alpha}_{\square}+O(d^{-2}\log d)$; (3) then follows from the above estimate on $W(z)$. The bounds (4) are easily obtained by estimating $\Phi^{\prime}$ near $\alpha_{\square}$ and recalling that $\Phi^{\prime\prime}<0$. ∎

2. Coarsening algorithm and frozen model

Coarsening algorithm. Set $\underline{\smash{\eta}}^{0}\equiv\underline{\smash{x}}$.

Denote the terminal configuration $\underline{\smash{\eta}}\equiv\underline{\smash{\eta}}(\underline{\smash{x}})\equiv\underline{\smash{\eta}}^{t+1}$. Write $\underline{\smash{m}}\subseteq E$ for the set of all matched free pairs formed during Step 1 of the coarsening process.

The idea is that the pre-image of any $\underline{\smash{\eta}}$ under the coarsening algorithm constitutes a cluster of independent set configurations — a set of configurations connected by (sequences of) local changes, in our setting by making neighboring 0/1 swaps. An important property of a coarsened configuration is that every 0-vertex has at least two 1-neighbors: as this is a rigid local configuration (a 0/1 swap across an edge cannot be made without violating the hard-core constraint), we have some indication (non-rigorously) that different clusters will be well separated in some sense. Note that Step 2 of the coarsening algorithm is needed to ensure this property even when the initial configuration is a maximum independent set: consider for example 0 — 1 — 0 — 1 — 0 arranged in a $5$-cycle such that every neighbor not on the cycle is a 0-vertex with many 1-neighbors. This can be part of a maximal configuration, but Step 1 results with f $\mathrel{{\mathop{\text{---}}\limits}}$ f — f $\mathrel{{\mathop{\text{---}}\limits}}$ f — 0 on the cycle where $m$ indicates a matched pair and the last 0 has no 1-neighbors. The purpose of this section is show that we may discard these odd-cycle scenarios and still recover the sharp asymptotics for $\bm{A}_{n}$.

In the subgraph $\mathfrak{F}(\underline{\smash{\eta}})\subseteq G$ induced by the f-vertices, every connected component either is not a tree, or is a tree with a (necessarily unique) perfect matching. To be precise, since we regard $G$ as a matching on the set $[nd]$ of labelled half-edges incident to vertices, $\mathfrak{F}$ shall be regarded as a matching on a subset of $[nd]$.

A (weighted) frozen model configuration $\bm{\underline{\smash{\overline{\eta}}}}\equiv(\underline{\smash{\eta}},\underline{\smash{m}})$ on $G$ is a unweighted frozen model configuration $\underline{\smash{\eta}}$ together with a perfect matching $\underline{\smash{m}}$ on $\mathfrak{F}(\underline{\smash{\eta}})$: equivalently, every $v\in V$ satisfies

The intensity of $\bm{\underline{\smash{\overline{\eta}}}}$ is the number of 1-vertices plus the number of matched f-pairs:

We shall always assume that the normalized intensity $\alpha$ lies in a restricted regime:

We now describe our reduction from the independent set model to the frozen model.

The proof is given in §5 (making use of §2 and §3).

We prove the theorem relying on Propns. 2.7 and 2.8 which will be proved in the remainder of this section.

converges to zero as $C\to\infty$, uniformly in $n$. (In the above, the first inequality is by the coarsening algorithm, the second inequality is by Propn. 2.2 with $o_{n}(1)$ indicating an error which tends to zero as $n\to\infty$, and the rightmost expression tends to zero by Markov’s inequality and the chain of inequalities (11).)

and by Thm. 2 this converges to one as $C\to\infty$, uniformly in $n$. Combining with the upper bound proves that $\bm{A}_{n}-{\bar{\bm{A}}}_{n}$ is a tight random variable as claimed. ∎

The above equivalence between the maximum independent set size and the threshold of the frozen model is based on the following

3. Large components and trees with matchings

The three estimates marked ($\circ$) follow straightforwardly from the explicit expressions given above; the last estimate ($\star$) is deferred to a later section (Propn. 2.9).

Combining with (15) and simplifying gives

Regarding $[dk]$ as a set of half-edges with the $i$-th half-edge incident to vertex $\lceil i/k\rceil$, let $\text{\sc tpm}_{d,k}$ denote the number of ways that $2(k-1)$ elements of $[dk]$ can be used to form a graph on $[k]$ which is a spanning tree with perfect matching (meaning a perfect matching in the tree, not to be confused with a perfect matching of half-edges). Then, using (15),

Recalling (12) and arguing similarly as in the proof of Propn. 2.7 we have

4. Estimates on forcing constraints

In this subsection we estimate the probability cost of the constraint that each 0-vertex is forced by at least two neighboring 1-vertices.

where $0<\vartheta<1$ may be arbitrarily chosen.

Let $\varepsilon_{0}$ be a small constant uniform in $d$, and suppose

If $\xi$ is another vector with $|\xi_{\omega}/\zeta_{\omega}-1|\leq e^{-1}$ for all $\omega\in\mathscr{X}$, then

so clearly $\liminf_{\varepsilon\downarrow 0}\gamma_{\varepsilon,\omega}$ must also be finite. It follows by an easy compactness argument that $\gamma_{\varepsilon}$ converges in the limit $\varepsilon\downarrow 0$ to the required solution $\gamma$ of $\Lambda_{\theta}^{\prime}(\gamma)=d\zeta$.

where $(\widetilde{X}_{t})_{t\geq 0}$ is an independent realization of the random walk $X$. Maximizing over all possible $k,x$ and applying 24 gives

Write $p_{\mu}$ for the law of $X\equiv X_{d}$ and $q_{\mu}$ for the law of $X_{d-1}$, and observe that $x_{\omega}p_{\mu}(x)=d\mu_{\omega}q_{\mu}(x-\mathbf{1}_{\omega})$ (with both sides zero for $x_{\omega}=0$). We then calculate

implying the stated bound on $\gamma_{\omega}=\log(z_{\theta,\gamma}\mu_{\omega}/\theta_{\omega})$, $\omega\in\mathscr{X}$. ∎

It follows (see e.g. [14, Lem. 2.3.9]) that with $\theta,\zeta$ in the stated regime, the Fenchel-Legendre transform $\Lambda_{\theta}^{*}(d\zeta)\equiv\sup_{\gamma}[\langle\gamma,d\zeta\rangle-\Lambda_{\theta}(\gamma)]$ of the cumulant generating function is given by

Since $\Lambda_{\theta}$ is strictly convex, we find by implicit differentiation that $\gamma$ is differentiable with respect to $\zeta$ (in the stated regime). We then see from (27) that $\Lambda_{\theta}^{*}$ is differentiable with respect to $\zeta$, with gradient $(\Lambda_{\theta}^{*})^{\prime}(d\zeta)=\gamma$.

where we introduced a Lagrangian term which clearly has no effect on the constrained space. In the denominator, Stirling’s approximation gives

We can estimate this easily by taking $\theta=\zeta$. Since $e^{\langle\gamma,x\rangle}p_{\theta}(x)=(z_{\theta,\gamma})^{d}p_{\mu}(x)$, it follows from (25) and (26) that

For $|\xi_{\omega}/\zeta_{\omega}-1|\leq e^{-1}$ it is straightforward to estimate $ndH(\xi\,|\,\zeta)\lesssim nd\|\xi-\zeta\|_{1}$, and combining these estimates concludes the proof of the proposition. ∎

First moment of frozen model

We shall specify a Gibbs measure $\nu$ on $\smash{T_{d}}$ by defining a consistent family of finite-dimensional distributions $\nu_{t}$ on the depth-$t$ subtrees $\smash{T_{d}}(t)$. A typical manner of specifying $\nu_{t}$ is to specify a law on some boundary conditions at depth $t$, and then to define $\nu_{t}$ as the law of the configuration on $\smash{T_{d}}(t)$ given the (random) boundary conditions.

In our setting some difficulty is imposed by the fact that the frozen model is not a factor model (or Markov random field) in the conventional sense that $\underline{\smash{\eta}}|_{A}$ and $\underline{\smash{\eta}}|_{B}$ are conditionally independent given the configuration $\underline{\smash{\eta}}|_{C}$ on any subset $C$ separating $A$ from $B$ — in particular, given the spins at level $t$ of $\smash{T_{d}}$, whether a vertex at level $t-1$ is required to take spin 1 depends on whether its neighboring 0’s in level $t$ are forced or not by 1’s in level $t+1$. Also, the frozen model spins $\underline{\smash{\eta}}$ do not encode the matching $\underline{\smash{m}}$ on the f-vertices.

The message-passing rule for our frozen model is

See Fig. 1 for an illustration: in each panel of the figure, the entire configuration of messages and vertex spins is uniquely determined by the messages incoming at the boundary of the subtree depicted.

In the following, to emphasize the dependence on $\lambda$ we sometimes write $\nu\equiv\nu^{\lambda}$, $q\equiv q^{\lambda}$.

2. Auxiliary model and Bethe variational principle

Recall our definition of the random $d$-regular graph $\smash{\mathcal{G}_{n,d}}$ as given by a uniformly random matching $M$ on half-edges $H=[nd]$ incident to vertices $V=[n]$. For convenience, we now bisect each edge in $\smash{\mathcal{G}_{n,d}}$ by a new clause vertex $a$, and refer to the resulting graph as the $(d,2)$-regular bipartite factor graph: this graph has vertex set $V\cup F$ with bipartition into the set $V$ of variables (vertices in the original graph) and the set $F$ of clauses (edges in the original graph). The new graph has edge set $E$ where $(ia)\in E$ ($i\in V$, $a\in F$) indicates that in the original graph vertex $i$ is incident to edge $a$. These edges are labelled, thus the new bipartite graph is simply equivalent to the original graph $G=(V,M,H)$ together with a labelling on $M$ as well as an ordering within each pair formed by $M$: this contributes a factor $(nd/2)!2^{nd/2}$ to the enumeration but clearly the problem remains unchanged, so we shall continue to use the notation $\smash{\mathcal{G}_{n,d}}$ for the $(d,2)$-regular bipartite factor graph.

The weight of configuration ${\underline{\smash{\sigma}}}\in\mathscr{M}^{E}$ under the auxiliary model is given by

Let $\bm{\Delta}$ denote the space of probability measures $\bm{h}\equiv(\bm{\mathchoice{\dot{h}}{\smash{\dot{h}}}{\dot{h}}{\dot{h}}},\bm{\mathchoice{\hat{h}}{\smash{\hat{h}}}{\hat{h}}{\hat{h}}})$ on $\supp\varphi$ (i.e., $\bm{\mathchoice{\dot{h}}{\smash{\dot{h}}}{\dot{h}}{\dot{h}}}$ is a probability measure on $\supp\mathchoice{\dot{\varphi}}{\smash{\dot{\varphi}}}{\dot{\varphi}}{\dot{\varphi}}$ while $\bm{\mathchoice{\hat{h}}{\smash{\hat{h}}}{\hat{h}}{\hat{h}}}$ is a probability measure on $\supp\mathchoice{\hat{\varphi}}{\smash{\hat{\varphi}}}{\hat{\varphi}}{\hat{\varphi}}$) such that

Let $\bm{\Delta}_{\alpha}$ denote the subspace of measures $\bm{h}\in\bm{\Delta}$ with normalized intensity

We shall show (Lem. 5.4) that $H_{\bm{\Delta}}$ is surjective, therefore $\bm{\Delta}$ is an $(\bm{\mathchoice{\dot{s}}{\smash{\dot{s}}}{\dot{s}}{\dot{s}}}-1)$-dimensional space with $\bm{\Delta}_{\alpha}$ an $(\bm{\mathchoice{\dot{s}}{\smash{\dot{s}}}{\dot{s}}{\dot{s}}}-2)$-dimensional subspace.

The expected number of auxiliary configurations on $\smash{\mathcal{G}_{n,d}}$ with empirical measure $\bm{h}$ is

If further $\min\bm{h}\gtrsim_{d}1$ as $n\to\infty$, then

Clearly an analogous expansion holds for the expectation of the $\lambda$-weighted partition function $\bm{Z}^{\lambda}(\bm{h})=\lambda^{n\,\mathbf{i}(\bm{h})}\bm{Z}(\bm{h})$; we write $\bm{\Phi}^{\lambda}(\bm{h})=\bm{\Phi}(\bm{h})+\mathbf{i}(\bm{h})\log\lambda$ for the associated rate function (with $\varphi^{\lambda}$ in place of $\varphi$).

The fugacity parameter $\lambda$ serves the purpose of a Lagrange multiplier: if $\bm{h}\in\bm{\Delta}_{\alpha}$ is a stationary point of $\bm{\Phi}$ restricted to $\bm{\Delta}_{\alpha}$, then for some $\lambda$ it must be a stationary point of $\bm{\Phi}^{\lambda}$ on the unrestricted space $\bm{\Delta}$. Strictly positive measures $\bm{h}$ which are stationary for $\bm{\Phi}^{\lambda}$ as a function on $\bm{\Delta}$ (unrestricted) correspond to a generalization of the tree Gibbs measures considered in §3.1, where the boundary conditions are specified by a law on incoming and outgoing messages, as we now describe. Let $\smash{T_{d,2}}$ denote the infinite tree given by bisecting each edge of $\smash{T_{d}}$ by a new (clause) vertex; this is the local weak limit of the random $(d,2)$-regular bipartite factor graph. The vertices at level $t$ of $\smash{T_{d,2}}$ are variables for $t$ odd, clauses for $t$ even. If ${\underline{\smash{\sigma}}}$ is a message configuration on the edges of $\smash{T_{d,2}}(t)$ — including the edges $E(t-1,t)$ joining levels $t-1$ and $t$ — then let $\Psi^{\lambda}_{t}({\underline{\smash{\sigma}}})$ denote the product of the factor weights $\mathchoice{\dot{\varphi}}{\smash{\dot{\varphi}}}{\dot{\varphi}}{\dot{\varphi}}^{\lambda}(\underline{\smash{\mathchoice{\dot{\sigma}}{\smash{\dot{\sigma}}}{\dot{\sigma}}{\dot{\sigma}}}}_{v})$, $\mathchoice{\hat{\varphi}}{\smash{\hat{\varphi}}}{\hat{\varphi}}{\hat{\varphi}}^{\lambda}(\underline{\smash{\mathchoice{\hat{\sigma}}{\smash{\hat{\sigma}}}{\hat{\sigma}}{\hat{\sigma}}}}_{a})$ over all $v,a\in\smash{T_{d,2}}(t-1)$. For probability measures $\mathchoice{\dot{h}}{\smash{\dot{h}}}{\dot{h}}{\dot{h}},\mathchoice{\hat{h}}{\smash{\hat{h}}}{\hat{h}}{\hat{h}}$ on $\mathscr{M}$ we define the measures

with $Z_{t}$ the normalizing constant which makes $\bm{\nu}_{t}$ a probability measure. We suppress the $\lambda$-dependence from the notation except to differentiate $\varphi^{\lambda}$ from $\varphi\equiv\varphi^{\lambda}|_{\lambda=1}$. The family $(\bm{\nu}_{t})_{t}$ is consistent if and only if $h\equiv(\mathchoice{\dot{h}}{\smash{\dot{h}}}{\dot{h}}{\dot{h}},\mathchoice{\hat{h}}{\smash{\hat{h}}}{\hat{h}}{\hat{h}})$ satisfies the Bethe recursions

(with $\mathchoice{\dot{z}}{\smash{\dot{z}}}{\dot{z}}{\dot{z}},\mathchoice{\hat{z}}{\smash{\hat{z}}}{\hat{z}}{\hat{z}}$ the normalizing constants). We show below that (as expected from our definition) these recursions are a generalization of the frozen model recursions (28). Thus a solution $h$ of (34) specifies a Gibbs measure $\bm{\nu}\equiv\bm{\nu}^{\lambda}$ for the auxiliary model on $\smash{T_{d,2}}$ which generalizes the measures $\nu\equiv\nu^{\lambda}$ described in §3.1.

If (36) holds, then (34) reduces to the frozen model recursions (28) with

proving our claim that the measures $\bm{\nu}$ generalize the measures $\nu$ of §3.1. The connection between these Gibbs measures and the rate function $\bm{\Phi}^{\lambda}$ is given by the following variational principle:

If a measure $\bm{h}$ in the interior $\bm{\Delta}^{\circ}$ of $\bm{\Delta}$ is stationary for $\bm{\Phi}^{\lambda}$, then $\bm{h}$ corresponds to a solution $h\equiv h^{\lambda}$ of the Bethe recursions (34) via

with $\bm{\mathchoice{\dot{z}}{\smash{\dot{z}}}{\dot{z}}{\dot{z}}},\bm{\mathchoice{\hat{z}}{\smash{\hat{z}}}{\hat{z}}{\hat{z}}},\bar{z}$ normalizing constants satisfying $\bar{z}=\bm{\mathchoice{\dot{z}}{\smash{\dot{z}}}{\dot{z}}{\dot{z}}}/\dot{z}=\bm{\mathchoice{\hat{z}}{\smash{\hat{z}}}{\hat{z}}{\hat{z}}}/\mathchoice{\hat{z}}{\smash{\hat{z}}}{\hat{z}}{\hat{z}}$ for $\mathchoice{\dot{z}}{\smash{\dot{z}}}{\dot{z}}{\dot{z}},\mathchoice{\hat{z}}{\smash{\hat{z}}}{\hat{z}}{\hat{z}}$ as in (34).

Follows from upon verifying that $\mathchoice{\dot{H}}{\smash{\dot{H}}}{\dot{H}}{\dot{H}},\mathchoice{\hat{H}}{\smash{\hat{H}}}{\hat{H}}{\hat{H}}$ are surjective; we will prove a stronger condition than surjectivity in Lem. 5.4 and (70). ∎

Recall now that our aim is to locate the global maximizer of $\bm{\Phi}$ on $\bm{\Delta}_{\alpha}$ as a stationary point of $\bm{\Phi}^{\lambda}$ for some value of $\lambda$.

In view of Lem. 3.3 and our preceding discussion of Gibbs measures and Lagrange multipliers, Thm. 3.4 will follow by showing

Any global maximizer ${}^{\star}\bm{h}_{\alpha}$ of $\bm{\Phi}$ on $\bm{\Delta}_{\alpha}$ lies in the interior $\bm{\Delta}^{\circ}_{\alpha}$. Thus for some Eventually we will find $\lambda=\lambda_{\star}=\exp\{-({}^{\star}\bm{\Phi})^{\prime}(\alpha)\}$. $\lambda$ it is a stationary point of $\bm{\Phi}^{\lambda}$, and hence corresponds via (38) to a solution $h\equiv h_{\alpha}$ of the Bethe recursions (34).

Ruling out boundary maximizers for $\bm{\Phi}$ is relatively easy, so we defer the proof to §4 where we will use the same argument to rule out boundary maximizers for the second-moment exponent ${}_{2}\hskip-2.0pt\bm{\Phi}$. We turn now to the more delicate task of proving the symmetries (36).

3. Bethe recursion symmetries

Suppose ${}^{\star}\bm{h}_{\alpha}$ is an interior maximizer for $\bm{\Phi}$ on $\bm{\Delta}_{\alpha}$, and so corresponds to a Bethe solution $h\equiv h^{\lambda}$. Let $\smash{\acute{T}_{d,2}}$ denote $\smash{T_{d,2}}$ with a subtree incident to the root removed, such that one clause $a\in\partial o$ is incident to an unmatched half-edge $\acute{e}$ (Fig. 2). Consider defining a Gibbs measure for $\varphi^{\lambda}$ on $\smash{\acute{T}_{d,2}}$ in the manner of (33), with boundary law given by $h$. Then the marginal law of $\sigma_{\acute{e}}$ will be $\mathchoice{\hat{h}}{\smash{\hat{h}}}{\hat{h}}{\hat{h}}$, and the marginal law of the $d$-tuple of spins incident to any given vertex will be $\bm{\mathchoice{\dot{h}}{\smash{\dot{h}}}{\dot{h}}{\dot{h}}}$. Further, the Gibbs measure on $\smash{\acute{T}_{d,2}}$ can be generated in Markovian fashion, starting with spin $\sigma_{\acute{e}}$ distributed according to $\mathchoice{\hat{h}}{\smash{\hat{h}}}{\hat{h}}{\hat{h}}$, generating the messages on the other $d-1$ edges incident to $o$ according to the conditional measure $\bm{\mathchoice{\dot{h}}{\smash{\dot{h}}}{\dot{h}}{\dot{h}}}(\underline{\smash{\mathchoice{\dot{\sigma}}{\smash{\dot{\sigma}}}{\dot{\sigma}}{\dot{\sigma}}}}\,|\,\sigma_{1}=\sigma_{\acute{e}})$, and continuing iteratively down the tree.

We shall assume that the maximizer ${}^{\star}\bm{h}_{\alpha}$ of $\bm{\Phi}$ on $\bm{\Delta}_{\alpha}$ lies in the interior $\bm{\Delta}^{\circ}_{\alpha}$, deferring the proof to §4 (see Propn. 4.5 and Cor. 4.8).

4. Explicit form of first moment exponent

where $\lambda$ and $q$ are determined from $\alpha$ via

Explicit Bethe prediction. Substituting (38) into (31) and rearranging gives

We use (37) to calculate $\bar{z},\bm{\mathchoice{\dot{z}}{\smash{\dot{z}}}{\dot{z}}{\dot{z}}},\bm{\mathchoice{\hat{z}}{\smash{\hat{z}}}{\hat{z}}{\hat{z}}}$ in terms of $q,\lambda$:

The recursion (28) also gives the expressions in (43) for $\lambda$ and $\alpha$ solely in terms of $q$. The mapping $q\mapsto\alpha$ is not one-to-one on the entire interval $0\leq q\leq 1$, but recalling (40) we must have $q=x(\log d)/d$ for $1.6\leq x\leq 3$, and on this interval it is easily verified that the mapping is indeed one-to-one, with $\lambda=d^{x}q[1+O(d^{-1}(\log d)^{2})]$ and $D_{q}\,\alpha=1+O(d^{-1/2})$ where $D_{q}$ denotes the total derivative with respect to $q$. This completes the verification of (43); it then follows from Thm. 3.4 that ${}^{\star}\bm{\Phi}(\alpha)={}^{\star}\bm{\Phi}^{\lambda}({}^{\star}\bm{h}^{\lambda})-\alpha\log\lambda$ is given by (42). We note here that ${}^{\star}\bm{\Phi}^{\prime}(\alpha)=-\log\lambda$, therefore ${}^{\star}\bm{\Phi}^{\prime\prime}(\alpha)=-(D_{q}\alpha)^{-1}D_{q}(\log\lambda)=-d[1+O((\log d)^{-1})]$.

Comparison of first-moment exponents. By contrast, the original independent set partition function has first-moment exponent $\Phi(\alpha)$ calculated in (6). This exponent also has a Bethe variational characterization, which can be expressed in terms of the fixed point $\acute{q}$ of the hard-core tree recursions:

This formula can be derived loosely in the same manner as (42); its validity can be checked simply by verifying that it agrees with (6). The relation between $\alpha,\acute{q}$ is given by $\alpha=\acute{\alpha}(\acute{q})=\acute{q}/(1+\acute{q})$, $\acute{q}=\acute{\alpha}^{-1}(\alpha)=\alpha/(1-\alpha)$, so we compare ${}^{\star}\bm{\Phi}(\alpha)$ and $\Phi(\alpha)$ by expressing both in terms of $q$: ${}^{\star}\bm{\Phi}(\alpha)$ is given by (42) with $\alpha,\lambda$ defined in terms of $q$ by (43), while

Let us emphasize that $q$ and $\acute{q}$ are not equal but rather are related through the same $\alpha$; explicitly $\acute{q}=q(1-q+\mathchoice{\tfrac{dq}{2\lambda}}{\smash{\tfrac{dq}{2\lambda}}}{\tfrac{dq}{2\lambda}}{\tfrac{dq}{2\lambda}})/(1-q-\mathchoice{\tfrac{d-2}{2\lambda}}{\smash{\tfrac{d-2}{2\lambda}}}{\tfrac{d-2}{2\lambda}}{\tfrac{d-2}{2\lambda}}q^{2})$. A little algebra then gives

Taylor expanding (recalling $q=x(\log d)/d$, $\lambda=d^{x}q[1+O(d^{-1}(\log d)^{2})]$) gives

Substituting into the above expression for $(\Phi-\bm{\Phi})(\alpha)$ and expanding the other terms gives

so the gap between the threshold is given by

For a more precise estimate, recall from Lem. 2.1 that $\alpha_{\square}=\widetilde{\alpha}_{\square}[1+O(d^{-1}\log d)]$ where $\widetilde{\alpha}_{\square}$ is the zero of $F(\alpha)\equiv\log(e/\alpha)-(d+1)\alpha/2$. Then

Substituting into the above gives (44), concluding the proof. ∎

Second moment of frozen model

The rate function ${}_{2}\hskip-2.0pt\bm{\Phi}$ on $\smash{{}_{2}\hskip-1.0pt\bm{\Delta}_{\alpha}}$ attains its maximum only at the product measure ${}^{\star}_{2}\bm{h}_{\alpha}\equiv{}^{\star}\bm{h}_{\alpha}\otimes{}^{\star}\bm{h}_{\alpha}$ or at the measure ${}^{\cdot\cdot}_{\hskip 1.0pt2}\hskip-1.0pt\bm{h}_{\alpha}$ with marginals ${}^{\star}\bm{h}_{\alpha}$ which is supported on pair configurations ${\underline{\smash{\tau}}}\equiv({\underline{\smash{\sigma}}},{\underline{\smash{\sigma}}})$.

Given a pair frozen configuration $\bm{\underline{\smash{\overline{\eta}}}}^{i}\equiv(\underline{\smash{\eta}}^{i},\underline{\smash{m}}^{i})$ ($i=1,2$) on $G$, define

(recalling that $\bm{Z}$ refers to the frozen model while $Z$ refers to the independent set model).

Let $\pi\in\mathcal{M}(n\alpha,n\rho)$; we decompose the expected contribution from $\pi$ to the pair frozen model partition function as

The procedure succeeds if and only if the final pair remaining is not already present in $\underline{\smash{m}}^{2}$. To bound the probability that it fails, note that if given a failed matching in which the final pair is already present in $\underline{\smash{m}}^{2}$, we can choose any of the first $(a^{\bullet}/2)-1$ pairs, and switch the half-edges in one of two ways to produce a valid matching (Fig. 3). Thus each failed matching maps to $a^{\bullet}-2$ valid matchings.

The function $g_{\alpha}$ has first derivative $(g_{\alpha})^{\prime}(\rho)=2\log(\alpha-\rho)-\log\rho-\log(1-2\alpha+\rho)+d\rho$; differentiating again gives $(g_{\alpha})^{\prime\prime}(\rho)=d-2(\alpha-\rho)^{-1}-\rho^{-1}-(1-2\alpha+\rho)^{-1}$, so we see that $g_{\alpha}$ is strictly convex on the interval $2/d\leq\rho\leq\alpha-3/d$. From the expression for $(g_{\alpha})^{\prime}$ we see that the (unique) minimizer $\rho_{\circ}$ of $g_{\alpha}$ on this interval must lie near $(\log d)/d$, and so applying Propn. 4.2 gives

We estimate $(g_{\alpha})^{\prime}(\rho)\leq-(\log d)/10$ for $d^{-1.85}\rho\leq 100/d$, and similarly $(g_{\alpha})^{\prime}(\rho)\geq(\log d)/10$ for $1.6(\log d)/d\leq\rho\leq\alpha-d^{-1.25}$. Thus

These estimates cover the entire interval $d^{-1.45}\leq\rho\leq\alpha-\varepsilon_{0}(\log d)/d$, implying the result. ∎

2. Boundary estimates

where $\star$ holds for $K,F$ appearing in the sum (51) with respect to the $\overline{\pi}$-configuration. Thus

For $d\geq d_{0}$, any global maximizer of $\bm{\Phi}$ on $\bm{\Delta}_{\alpha}$ must be strictly positive on $\supp\varphi$.

Fix any small constant $\varepsilon_{0}>0$ uniform in $d$. For $d\geq d_{0}(\varepsilon_{0})$, any global maximizer of ${}_{2}\hskip-2.0pt\bm{\Phi}$ on $\smash{{}_{2}\hskip-1.0pt\bm{\Delta}_{\alpha}}$ which lies outside of $\smash{{}^{\cdot\cdot}_{2}\hskip-1.0pt\bm{\Delta}_{\alpha}}$ must be strictly positive on $\supp\varphi_{2}$.

We shall prove (b); the proof of (a) is similar but simpler.

Boundary derivative of rate function. As we have noted before, the functional form of ${}_{2}\hskip-2.0pt\bm{\Phi}$ implies that the optimal $\bm{h}$ in $\smash{{}_{2}\hskip-1.0pt\bm{\Delta}_{\alpha}}$ must be symmetric, with

For $\bm{\delta}\equiv(\bm{\mathchoice{\dot{\delta}}{\smash{\dot{\delta}}}{\dot{\delta}}{\dot{\delta}}},\bm{\mathchoice{\hat{\delta}}{\smash{\hat{\delta}}}{\hat{\delta}}{\hat{\delta}}})$ such that $\bm{h}+t\bm{\delta}$ is also symmetric and lies in $\smash{{}_{2}\hskip-1.0pt\bm{\Delta}_{\alpha}}$ for $t\geq 0$ small, consider

To show that $\bm{h}$ is not a maximizer it suffices to exhibit $\mathbf{T}(_{2}\hskip-2.0pt\bm{\Phi})(\bm{h};\bm{\delta})>0$ for some $\bm{\delta}$. In particular, it follows by convexity that for any $\bm{h}\in\smash{{}_{2}\hskip-1.0pt\bm{\Delta}_{\alpha}}$, $\bm{h}+t({}^{\star}_{2}\bm{h}_{\alpha}-\bm{h})\in\smash{{}_{2}\hskip-1.0pt\bm{\Delta}^{\circ}_{\alpha}}$ for $t>0$ small and ${}^{\star}_{2}\bm{h}_{\alpha}$ as in the statement of Thm. 4.1. Therefore, if $\bm{h}$ is a maximizer such that the edge marginal has full support $\supp\mathchoice{\bar{h}}{\smash{\bar{h}}}{\bar{h}}{\bar{h}}=\mathscr{M}^{2}$, then necessarily $\supp\bm{h}=\supp\varphi_{2}$, since otherwise $\mathbf{T}(_{2}\hskip-2.0pt\bm{\Phi})(\bm{h};{}^{\star}_{2}\bm{h}_{\alpha}-\bm{h})>0$.

Recall (8) and Defn. 3.2 that we have truncated the frozen model and the spaces $\bm{\Delta}_{\alpha},\smash{{}_{2}\hskip-1.0pt\bm{\Delta}_{\alpha}}$ by restricting the density of f-variables, so in order to establish $\bm{\Phi}$ and ${}_{2}\hskip-2.0pt\bm{\Phi}$ have interior global maximizers in $\bm{\Delta}_{\alpha}$ and $\smash{{}_{2}\hskip-1.0pt\bm{\Delta}_{\alpha}}$ respectively, we must verify in addition to Propn. 4.5 that the maximizer does not occur near the boundary with density $\beta_{\max}$ of f-variables; this will be done in §4.3.

3. Near-independence regime

In this subsection we complete our analysis of the near-independence regime $\smash{{}^{\star}_{2}\hskip-1.0pt\bm{\Delta}_{\alpha}}$ to prove

The unique global maximizer of the restriction of ${}_{2}\hskip-2.0pt\bm{\Phi}$ to $\smash{{}^{\star}_{2}\hskip-1.0pt\bm{\Delta}_{\alpha}}$ is ${}^{\star}_{2}\bm{h}_{\alpha}$.

Let $\delta\equiv e^{-d^{2}}\min\{n_{\omega}:\omega\in\mathscr{P}\}$; then Propn. 4.4 implies that $\delta$ must scale linearly with $n$.

where we used that $(A+c)_{b}/(A)_{b}=\exp\{(bc/A)[1+O(x)]\}$ for $|b|,|c|\leq xA$. Thus

Any global maximizer of $\bm{\Phi}$ on $\bm{\Delta}_{\alpha}$ lies in the interior $\bm{\Delta}^{\circ}_{\alpha}$.

Any global maximizer of ${}_{2}\hskip-2.0pt\bm{\Phi}$ on $\smash{{}^{\star}_{2}\hskip-1.0pt\bm{\Delta}_{\alpha}}$ must be an interior stationary point.

Propn. 4.5a and Lem. 4.7a combine to give (a), while (b) follows by combining Cor. 4.3, Propn. 4.5b, and Lem. 4.7b. ∎

Cor. 4.8 was required in the proof of Thm. 3.4; it also implies (with Lem. 3.3) that any maximizer $\bm{h}$ on ${}_{2}\hskip-2.0pt\bm{\Phi}$ on $\smash{{}^{\star}_{2}\hskip-1.0pt\bm{\Delta}_{\alpha}}$ corresponds to a solution $h$ of the pair Bethe recursions for some $\lambda\equiv(\lambda_{1},\lambda_{2})$ ((38) and (34) with $\smash{\varphi_{2}^{\lambda}\equiv\varphi^{\lambda_{1}}\otimes\varphi^{\lambda_{2}}}$ in place of $\varphi^{\lambda}$). It remains to identify this Bethe solution with the one corresponding to ${}^{\star}_{2}\bm{h}_{\alpha}={}^{\star}\bm{h}_{\alpha}\otimes{}^{\star}\bm{h}_{\alpha}$.

with the rest being determined by margin constraints. Clearly $\smash{q^{\lambda_{1}}\otimes q^{\lambda_{2}}}$ solves (56), and the following lemma identifies a regime in which it is the unique solution:

As noted above, Cor. 4.8b implies that any maximizer $\bm{h}$ of ${}_{2}\hskip-2.0pt\bm{\Phi}$ on $\smash{{}^{\star}_{2}\hskip-1.0pt\bm{\Delta}_{\alpha}}$ corresponds to a solution $h$ of the pair Bethe recursions (34) with respect to some $\smash{\varphi^{\lambda_{1}}\otimes\varphi^{\lambda_{2}}}$. We now show that $h$ must satisfy the Bethe symmetries $\mathchoice{\hat{h}}{\smash{\hat{h}}}{\hat{h}}{\hat{h}}(\bm{io})=\mathchoice{\hat{h}}{\smash{\hat{h}}}{\hat{h}}{\hat{h}}(\bm{i}^{\prime}\bm{o})$, where $\bm{i}$ or $\bm{i}^{\prime}$ now indicates the incoming pair of variable-to-clause messages, and $\bm{o}$ the outgoing pair of clause-to-variable messages.

This proves the symmetries $\mathchoice{\hat{h}}{\smash{\hat{h}}}{\hat{h}}{\hat{h}}(\bm{io})=\mathchoice{\hat{h}}{\smash{\hat{h}}}{\hat{h}}{\hat{h}}(\bm{i}^{\prime}\bm{o})$, so we conclude that $h$ must in fact correspond to a solution $\bm{q}$ of the pair frozen model recursions (56) via $9\,\mathchoice{\hat{h}}{\smash{\hat{h}}}{\hat{h}}{\hat{h}}(\bm{io})=\bm{q}_{\bm{o}}$ (cf. (37)). It remains to verify that $\bm{q}$ falls within the regime of Lem. 4.9. As before, let $K$ denote the number of 01–10 edges: from (38) and the $h$-to-$\bm{q}$ correspondence,

4. A priori rigidity estimate

In this section we analyze near-identical frozen model configurations to prove

The proof of Propn. 4.10 is based on an a priori estimate showing that frozen model configurations are sufficiently rigid that one typically does not find a large cluster of configurations near a given one. For application in our proof of the tightness of $\bm{A}_{n}$ we shall prove this estimate for graphs drawn from the following slight generalization of the configuration model which allows for some unmatched edges (Fig. 5). Let $V$ be a set of $n$ vertices, each incident to $d$ half-edges. Let $\mathcal{Y}^{\star}$ be a disjoint set of $\bm{y}\lesssim_{d}\log n$ vertices, each incident to a single half-edge. Finally let $F$ be a set of $(nd+\bm{y})/2$ clauses, each incident to $2$ half-edges. Let $G^{\partial}$ be the graph formed by taking a random matching between the half-edges incident to $V^{\partial}\equiv V\cup\mathcal{Y}^{\star}$ with the half-edges incident to $F$. We shall write $F^{\partial}\equiv\partial\mathcal{Y}^{\star}\subseteq F$, $\mathcal{Y}\equiv V\cap\partial F^{\partial}$, and $\mathcal{R}\equiv V\backslash\mathcal{Y}$.

For $S,S^{\prime}\subseteq V^{\partial}$ write $F(S,S^{\prime})$ for the set of clauses $a\in F$ joining a vertex in $S$ to a vertex in $S^{\prime}$; write $F(S)\equiv F(S,S)$ for the clauses internal to $S$.

Write $\mathscr{Y}$ for the half-edges joining $\mathcal{Y}$ to $F^{\partial}$. In the following, we fix boundary conditions given by a auxiliary pair configuration ${\underline{\smash{\tau}}}_{\mathscr{Y}}\equiv({\underline{\smash{\sigma}}}^{1}_{\mathscr{Y}},{\underline{\smash{\sigma}}}^{2}_{\mathscr{Y}})$ on $\mathscr{Y}$. Let ${}_{2}\hskip-1.0pt\bm{Z}^{\partial}[\pi|{\underline{\smash{\tau}}}_{\mathscr{Y}}]$ denote the cardinality of the set ${}_{2}\bm{O}^{\partial}[\pi|{\underline{\smash{\tau}}}_{\mathscr{Y}}]$ of pair frozen model configurations on $G^{\partial}$ which are consistent with ${\underline{\smash{\tau}}}_{\mathscr{Y}}$ and have empirical measure $\pi_{\omega}=\bm{r}_{\omega}/\bm{r}$ when restricted to $\mathcal{R}$. We decompose

where ${}_{2}\bm{O}^{\partial}_{A}[\pi|{\underline{\smash{\tau}}}_{\mathscr{Y}}]\subseteq{}_{2}\bm{O}^{\partial}[\pi|{\underline{\smash{\tau}}}_{\mathscr{Y}}]$ denotes the subset of configurations which have $\gamma/2\equiv|F(V_{\neq})|=\bm{\rho}+A$ internal edges among the unequal spins. It is straightforward to see that $A\geq 0$; we show a stronger inequality in Lem. 6.5. We shall compare the expectation of ${}_{2}\hskip-1.0pt\bm{Z}^{\partial}_{A}[\pi|{\underline{\smash{\tau}}}_{\mathscr{Y}}]$ with that of $\bm{Z}^{\partial}[\pi^{1}|{\underline{\smash{\sigma}}}^{1}_{\mathscr{Y}}]$ — the number of frozen model configurations on $G^{\partial}$ which are consistent with ${\underline{\smash{\sigma}}}^{1}_{\mathscr{Y}}$ and have empirical measure given by the projection $\pi^{1}$ of $\pi$ onto the first coordinate:

Note $\bm{Z}^{\partial}[\pi^{1}|{\underline{\smash{\sigma}}}^{1}_{\mathscr{Y}}]=\text{{proj}}^{1}({}_{2}\bm{O}^{\partial}[\pi|{\underline{\smash{\tau}}}_{\mathscr{Y}}])$ where $\text{{proj}}^{1}$ is the projection mapping $(\bm{\underline{\smash{\overline{\eta}}}}^{1},\bm{\underline{\smash{\overline{\eta}}}}^{2})\mapsto\bm{\underline{\smash{\overline{\eta}}}}^{1}$.

provided $\Delta\equiv\bm{\rho}+\bm{\varepsilon}\leq n\varepsilon_{0}(\log d)/d$.

Because of the restriction to $V_{=}$, in the current setting the method of Propn. 4.2 reduces to a first-moment calculation, yielding

Combinatorial factors. The preceding estimates were for a fixed configuration $\underline{\smash{\omega}}\in\mathscr{P}^{V^{\partial}}$ consistent with ${\underline{\smash{\tau}}}_{\mathscr{Y}},\pi$. Accounting for the permutations of $\underline{\smash{\omega}}$ and $\underline{\smash{\eta}}^{1}$ gives (recalling $\bm{r}=|\mathcal{R}|$)

To see the last inequality, note the sum over $A\geq 0$ is clearly $\lesssim 1$ if $C\Delta^{2}d\leq 2n\gamma$. If $C\Delta^{2}d>2n\gamma$, then recalling $\bm{\rho}\leq\gamma/2$ and optimizing over $\gamma$ gives $(\bm{\rho}/\gamma)^{\bm{\rho}}(C\Delta^{2}d/(n\gamma))^{A}\leq d^{O(\Delta\varepsilon_{0})}$. It follows that there exists a small constant $\varepsilon_{0}$ (uniform in $d$) such that

Follows from Propn. 4.12 applied to our original random graph $\smash{\mathcal{G}_{n,d}}$ with no unmatched edges. ∎

Follows by combining Propns. 4.6 and 4.10. ∎

Negative-definiteness of free energy Hessians

In this section we prove Thm. 2.5 as well as

For $d\geq d_{0}$, the Hessians $H\bm{\Phi}({}^{\star}\bm{h}_{\alpha})$ and $H(_{2}\hskip-2.0pt\bm{\Phi})({}^{\star}_{2}\bm{h}_{\alpha})$ as functions on $\bm{\Delta}_{\alpha}$ and $\smash{{}_{2}\hskip-1.0pt\bm{\Delta}_{\alpha}}$ respectively are negative-definite.

The calculation of this section is similar to that of [15, §7]. Let $\bm{h}\in\bm{\Delta}^{\circ}_{\alpha}$ with $\bm{\mathchoice{\dot{h}}{\smash{\dot{h}}}{\dot{h}}{\dot{h}}}$ and $\bm{\mathchoice{\hat{h}}{\smash{\hat{h}}}{\hat{h}}{\hat{h}}}$ both symmetric, and let $\bm{\delta}$ be any signed measure on $\supp\varphi$ (not necessarily symmetric) with $\bm{h}+s\bm{\delta}\in\bm{\Delta}^{\circ}_{\alpha}$ for sufficiently small $|s|$. Then

where $a/b$ denotes the vector given by coordinate-wise division of $a$ by $b$, and $\langle\cdot\rangle_{h}$ denotes integration with respect to measure $h$, e.g. $\langle(\mathchoice{\bar{\delta}}{\smash{\bar{\delta}}}{\bar{\delta}}{\bar{\delta}}/\mathchoice{\bar{h}}{\smash{\bar{h}}}{\bar{h}}{\bar{h}})^{2}\rangle_{\mathchoice{\bar{h}}{\smash{\bar{h}}}{\bar{h}}{\bar{h}}}=\sum_{\sigma}\mathchoice{\bar{\delta}}{\smash{\bar{\delta}}}{\bar{\delta}}{\bar{\delta}}(\sigma)^{2}/\mathchoice{\bar{h}}{\smash{\bar{h}}}{\bar{h}}{\bar{h}}(\sigma)$. Consider maximizing (62) over $\bm{\delta}$ subject to fixed marginals $\mathchoice{\bar{\delta}}{\smash{\bar{\delta}}}{\bar{\delta}}{\bar{\delta}}$: we find that the optimal $\bm{\mathchoice{\hat{\delta}}{\smash{\hat{\delta}}}{\hat{\delta}}{\hat{\delta}}}$ will be symmetric, with $\bm{\mathchoice{\hat{\delta}}{\smash{\hat{\delta}}}{\hat{\delta}}{\hat{\delta}}}(\sigma,\text{{R}}\sigma)=\mathchoice{\bar{\delta}}{\smash{\bar{\delta}}}{\bar{\delta}}{\bar{\delta}}(\sigma)=\mathchoice{\bar{\delta}}{\smash{\bar{\delta}}}{\bar{\delta}}{\bar{\delta}}(\text{{R}}\sigma)$. The optimal $\bm{\mathchoice{\dot{\delta}}{\smash{\dot{\delta}}}{\dot{\delta}}{\dot{\delta}}}$ will be of form $d\,\bm{\mathchoice{\dot{\delta}}{\smash{\dot{\delta}}}{\dot{\delta}}{\dot{\delta}}}(\underline{\smash{\mathchoice{\dot{\sigma}}{\smash{\dot{\sigma}}}{\dot{\sigma}}{\dot{\sigma}}}})=\bm{\mathchoice{\dot{h}}{\smash{\dot{h}}}{\dot{h}}{\dot{h}}}(\underline{\smash{\mathchoice{\dot{\sigma}}{\smash{\dot{\sigma}}}{\dot{\sigma}}{\dot{\sigma}}}})\sum_{i=1}^{d}\mathchoice{\dot{\chi}}{\smash{\dot{\chi}}}{\dot{\chi}}{\dot{\chi}}_{\sigma_{i}}$ with $\mathchoice{\dot{\chi}}{\smash{\dot{\chi}}}{\dot{\chi}}{\dot{\chi}}$ chosen to satisfy the margin constraint — which, after a little algebra, becomes the system of equations

where $\mathchoice{\bar{H}}{\smash{\bar{H}}}{\bar{H}}{\bar{H}}\equiv\diag(\mathchoice{\bar{h}}{\smash{\bar{h}}}{\bar{h}}{\bar{h}})$ and $\mathchoice{\dot{M}}{\smash{\dot{M}}}{\dot{M}}{\dot{M}}$ denotes the stochastic matrix with entries

If such $\mathchoice{\dot{\chi}}{\smash{\dot{\chi}}}{\dot{\chi}}{\dot{\chi}}$ exists, then the minimal value of $\langle(\bm{\mathchoice{\dot{\delta}}{\smash{\dot{\delta}}}{\dot{\delta}}{\dot{\delta}}}/\bm{\mathchoice{\dot{h}}{\smash{\dot{h}}}{\dot{h}}{\dot{h}}})^{2}\rangle_{\bm{\mathchoice{\dot{h}}{\smash{\dot{h}}}{\dot{h}}{\dot{h}}}}$ subject to marginals $\mathchoice{\bar{\delta}}{\smash{\bar{\delta}}}{\bar{\delta}}{\bar{\delta}}$ is $\langle\mathchoice{\bar{\delta}}{\smash{\bar{\delta}}}{\bar{\delta}}{\bar{\delta}},\mathchoice{\dot{\chi}}{\smash{\dot{\chi}}}{\dot{\chi}}{\dot{\chi}}\rangle$ (which clearly remains invariant under translations of $\mathchoice{\dot{\chi}}{\smash{\dot{\chi}}}{\dot{\chi}}{\dot{\chi}}$ by vectors in the kernel of $I+(d-1)\mathchoice{\dot{M}}{\smash{\dot{M}}}{\dot{M}}{\dot{M}}$).

Throughout the following we take $\bm{h}$ to be ${}^{\star}\bm{h}_{\alpha}$ (first moment) or ${}^{\star}_{2}\bm{h}_{\alpha}$ (second moment).

The eigenvalues of $\mathchoice{\dot{M}}{\smash{\dot{M}}}{\dot{M}}{\dot{M}}$ counted with geometric multiplicity are

where (using $\mathchoice{\bar{h}}{\smash{\bar{h}}}{\bar{h}}{\bar{h}}$-reversibility of $\mathchoice{\dot{M}}{\smash{\dot{M}}}{\dot{M}}{\dot{M}}$, or alternatively the frozen model recursion)

For the other two eigenvalues, consider the following “almost” eigenvalue equations:

so the last eigenvalue $\lambda_{2}$ must satisfy $|\lambda_{2}-(d-1)^{-1}|\leq d^{-1.2}$. Note however that

so $\lambda_{2}$ does not exactly equal $(d-1)^{-1}$. ∎

The eigenvalues of $\mathchoice{\dot{Q}}{\smash{\dot{Q}}}{\dot{Q}}{\dot{Q}}$ are given by

so $\mathchoice{\dot{Q}}{\smash{\dot{Q}}}{\dot{Q}}{\dot{Q}}$ is non-singular since we saw in Lem. 5.3 that $(d-1)^{-1}\notin\text{{{eigen}}}(\mathchoice{\dot{M}}{\smash{\dot{M}}}{\dot{M}}{\dot{M}})$. Since we proved in Thm. 3.4 that ${}^{\star}\bm{h}_{\alpha}\in\bm{\Delta}^{\circ}_{\alpha}$ is the global maximizer of $\bm{\Phi}$ on $\bm{\Delta}_{\alpha}$, the restriction of the above quadratic form to the space of permissible $\mathchoice{\bar{\delta}}{\smash{\bar{\delta}}}{\bar{\delta}}{\bar{\delta}}$ (formally, to $U^{t}\mathchoice{\bar{H}}{\smash{\bar{H}}}{\bar{H}}{\bar{H}}^{-1/2}\overline{W}$) must be negative semi-definite, so by non-singularity we see that it is in fact negative-definite.

The proof for the second moment Hessian $H(_{2}\hskip-2.0pt\bm{\Phi})({}^{\star}_{2}\bm{h}_{\alpha})$ on $\smash{{}_{2}\hskip-1.0pt\bm{\Delta}_{\alpha}}$ is similar; note ${}^{\star}_{2}\bm{h}_{\alpha}={}^{\star}\bm{h}_{\alpha}\otimes{}^{\star}\bm{h}_{\alpha}$ implies $\mathchoice{\dot{M}}{\smash{\dot{M}}}{\dot{M}}{\dot{M}}_{2}=\mathchoice{\dot{M}}{\smash{\dot{M}}}{\dot{M}}{\dot{M}}\otimes\mathchoice{\dot{M}}{\smash{\dot{M}}}{\dot{M}}{\dot{M}}$, with eigenvalues $\{\lambda\lambda^{\prime}:\lambda,\lambda^{\prime}\in\text{{{eigen}}}(\mathchoice{\dot{M}}{\smash{\dot{M}}}{\dot{M}}{\dot{M}})\}$. The kernel of $d^{-1}[I+(d-1)\mathchoice{\dot{M}}{\smash{\dot{M}}}{\dot{M}}{\dot{M}}_{2}]$ is spanned by vectors $\bar{x}\otimes\bar{y}$ or $\bar{y}\otimes\bar{x}$ with $\bar{x}$ as before and $\bar{y}$ any right eigenvector of $\mathchoice{\dot{M}}{\smash{\dot{M}}}{\dot{M}}{\dot{M}}_{2}$ with eigenvalue $1$, and again the permissible measures $\mathchoice{\bar{\delta}}{\smash{\bar{\delta}}}{\bar{\delta}}{\bar{\delta}}$ must be orthogonal to the kernel. Negative-definiteness then follows as above from the observation that $(d-1)^{-1}\notin\text{{{eigen}}}(\mathchoice{\dot{M}}{\smash{\dot{M}}}{\dot{M}}{\dot{M}}_{2})$. ∎

For any $\sigma,\sigma^{\prime}\in\mathscr{M}$ there exists a signed integer measure $\bm{\delta}\equiv\bm{\delta}_{\sigma-\sigma^{\prime}}=(\bm{\mathchoice{\dot{\delta}}{\smash{\dot{\delta}}}{\dot{\delta}}{\dot{\delta}}},\bm{\mathchoice{\hat{\delta}}{\smash{\hat{\delta}}}{\hat{\delta}}{\hat{\delta}}})$ with $\supp\bm{\delta}\subseteq\supp\varphi$ such that

The analogous condition holds for the support of the second-moment factors $\varphi_{2}$.

Constant fluctuations

The right-hand side tends to zero as $\varepsilon$ decreases to zero, proving the theorem. ∎

Assume throughout that $m^{\prime}\leq m-2$ with $m-m^{\prime}\lesssim_{d}\log n$. For such $m^{\prime}$, we showed in [15, §8] that the sum appearing in (65) has two dominant components: the first is an “independent-copies contribution” coming from pair configurations with empirical measure near ${}^{\star}_{2}\bm{h}_{\alpha}\equiv{}^{\star}\bm{h}_{\alpha}\otimes{}^{\star}\bm{h}_{\alpha}$; we showed that this contribution can be controlled under some abstract conditions (Lem. 6.2 and Cor. 6.3 below). The other component is an “identical-copies contribution” coming from closely correlated pair configurations: this was controlled in [15, §8] under the assumption that the first moment is exponentially large, and the main work of this section is to control the identical-copies contribution assuming only that the first moment is bounded below by a large constant. Before turning to this we first show in §6.1 that the independent-copies contribution is controlled by a straightforward application of the method of [15, §8].

$\mathscr{W}$ can only intersect $T$ in its leaves; and we shall let $\mathscr{U}$ denote the leaves of $T$ without $\mathscr{W}$.

Regarding $G$ as a $(d,2)$-regular graph of variables $V$ (degree $d$) and clauses $F$ (degree $2$), for $S\subseteq V\cup F$ and any configuration ${\underline{\smash{\sigma}}}_{S}$ on the edges incident to the vertices $s\in S$, let