Combinatorial approach to the interpolation method and scaling limits in sparse random graphs

Introduction

This conjecture is in fact just one of a family of similar conjectures. Consider, for example, the random MAX-K-SAT problem—the problem of finding the largest number of satisfiable clauses of size $K$ in a uniformly random instance of a K-SAT problem on $N$ variables with $cN$ clauses. This problem can be viewed as an optimization problem over a sparse random hypergraph. A straightforward argument shows that asymptotically as $N\rightarrow\infty$, at least $1-2^{-K}$ fraction of the clauses can be satisfied with high probability (w.h.p.). Indeed any random assignment of variables satisfies each clause with probability $1-2^{-K}$. It was conjectured in CopGamMohSor that the proportion of the largest number of satisfiable clauses has a limit w.h.p. as $N\rightarrow\infty$. As another example, consider the problem of partial $q$-coloring of a graph: finding a $q$-coloring of nodes which maximizes the total number of properly colored edges. It is natural to conjecture again that value of this maximum has a scaling limit w.h.p. (though we are not aware of any papers explicitly stating this conjecture).

Recently a powerful rigorous statistical physics method was introduced by Guerra and Toninelli GuerraTon and further developed by Franz and Leone FranzLeone , Franz, Leone and Toninelli FranzLeoneToninelliRegular , Panchenko and Talagrand PanchenkoTalagrand and Montanari MontanariLDPCInterpolation in the context of the theory of spin glasses. The method is based on an ingenious interpolation between a random hypergraph model on $N$ nodes on the one hand, and a disjoint union of random hypergraph models on $N_{1}$ and $N_{2}$ nodes, on the other hand, where $N=N_{1}+N_{2}$. Using this method it is possible to show for certain spin glass models on random hypergraphs, that when one considers the expected log-partition function, the derivative of the interpolation function has a definite sign at every value of the interpolation parameter. As a result the expected log-partition function of the $N$-node model is larger (or smaller depending on the details of the model) than the sum of the corresponding expected log-partition functions on $N_{1}$ and $N_{2}$-node models. This super(sub)-additivity property is used to argue the existence of the (thermodynamic) limit of the expected log-partition function scaled by $N$. From this property the existence of the scaling limits for the ground states (optimization problems described above) can also be shown by taking a limit as positive temperature approaches zero temperature. In FranzLeone , the method was used to prove the scaling limit of log-partition functions corresponding to random K-SAT model for even $K$, and also for the so-called Viana–Bray models with random symmetric Hamiltonian functions. The case of odd $K$ was apparently resolved later using the same method FranzMontanariPrivateCommunication .

Results and technical contributions. The goal of the present work is to simplify and extend the applicability of the interpolation method, and we do this in several important ways. First, we extend the interpolation method to a variety of models on Erdös–Rényi graphs not considered before. Specifically, we consider independent set, MAX-CUT, Ising, graph coloring (henceforth referred to as coloring), K-SAT and Not-All-Equal K-SAT (NAE-K-SAT) models. The coloring model, in particular, is of special interest as it is the first nonbinary model to which interpolation method is applied.

Second, we provide a simpler and a more combinatorial interpolation scheme as well as analysis. Moreover, we treat the zero temperature case (optimization problem) directly and separately from the case of the log-partition function, and again the analysis turns out to be substantially simpler. As a result, we prove the existence of the limit of the appropriately rescaled value of the optimization problems in these models, including the independent set problem, thus resolving the open problem stated earlier.

Third, we extend the above results to the case of random regular graphs (and hypergraph ensembles, depending on the model). The case of random regular graphs has been considered before by Franz, Leone and Toninelli FranzLeoneToninelliRegular for the K-SAT and Viana–Bray models with an even number of variables per clause, and Montanari MontanariLDPCInterpolation in the context of bounds on the performance of low density parity check (LDPC) codes. In fact, both papers consider general degree distribution models. The second of these papers introduces a multi-phase interpolation scheme. In this paper we consider a modification of the interpolation scheme used in FranzLeoneToninelliRegular and apply it to the same six models we are focusing in the case of Erdös–Rényi graph.

Finally, we prove the large deviation principle for the satisfiability property for coloring, K-SAT and NAE-K-SAT models on Erdös–Rényi graph in the following sense. A well-known satisfiability conjecture Friedgut states that for each of these models there exists a (model dependent) critical value $c^{*}$ such that for every $\varepsilon>0$, when the number of edges (or clauses for a SAT-type problem) is at most $(c^{*}-\varepsilon)N$, the model is colorable (satisfiable) w.h.p., and when it is at least $(c^{*}+\varepsilon)N$, it is not colorable (not satisfiable) w.h.p. as $N\rightarrow\infty$. Friedgut Friedgut came close to proving this conjecture by showing that these models exhibit sharp phase transition: there exists a sequence $c^{*}_{N}$ such that for every $\varepsilon$, the model is colorable (satisfiable) w.h.p. as $N\rightarrow\infty$ when the number of edges (clauses) is at most $(c_{N}^{*}-\varepsilon)N$, and is not colorable (satisfiable) w.h.p. when the number of edges (clauses) is at least $(c_{N}^{*}+\varepsilon)N$. It is also reasonable to conjecture (which in fact is known to be true in the case $K=2$), that not only the satisfiability conjecture is valid, but, moreover, the probability of satisfiability $p(c,N)$ decays to zero exponentially fast when $c>c^{*}$.

In this paper we show that for these three models, namely coloring, K-SAT and NAE-K-SAT, the limit $r(c)\triangleq\lim_{N\to\infty}N^{-1}\log p(c,N)$ exists for every $c$. Namely, while we do not prove the satisfiability conjecture and the exponential rate of convergence to zero of the satisfiability probability above the critical threshold, we do prove that if the convergence to zero occurs exponentially fast, it does so at a well-defined rate $r(c)$. Assuming the validity of the satisfiability conjecture and the exponential rate of decay to zero above $c^{*}$, our result implies that $r(c)=0$ when $c<c^{*}$ and $r(c)<0$ when $c>c^{*}$. Moreover, we show that our results would imply the satisfiability conjecture, if one could strengthen Friedgut’s result as follows: for every $\varepsilon>0$, $p(c_{N}^{*}+\varepsilon,N)$ converges to zero exponentially fast, where $c_{N}^{*}$ is the same sequence as in Friedgut’s theorem.

Organization of the paper. The remainder of the paper is organized as follows. In the following section we introduce the sparse random (Erdös–Rényi) and random regular (hyper)-graphs and introduce various combinatorial models of interest. Our main results are stated in Section 3. The proofs for the case of Erdös–Rényi graphs are presented in Section 4 for results related to combinatorial optimization, and in Section 5 for results related to the log-partition function. The proofs of results for random regular graphs are presented in Section 6. Several auxiliary technical results are established in the Appendices A and B. In particular we state and prove a simple modification of a classical super-additivity theorem: if a sequence is nearly super-additive, it has a limit after an appropriate normalization.

Sparse random hypergraphs

The reason for considering the more general case of hypergraphs is to capture combinatorial models with hyperedges. For example, in the case of K-SAT each clause contains $K\geq 2$ distinct nodes that can be considered as a hyperedge on $K$ nodes (more detail is provided below).

where $x_{e}=(x_{i},i\in e)$. Namely, $H(x)$ is the value associated with a chosen assignment $x$, and $H$ is the optimal value, or the groundstate in the statistical physics terminology. In many cases the node and edge potentials will be random functions generated i.i.d.; see examples below.

NAE-K-SAT (Not-All-Equal-K-SAT). The setting is as above except now we set $H_{e}(a_{1},\ldots,a_{K})=H_{e}(1-a_{1},\ldots,1-a_{K})=0$ and $H_{e}(x)=1$ for all other $x$ for each $e$.

It is for the K-SAT and NAE-K-SAT models that considering directed, as opposed to undirected, hypergraphs is convenient, as for these models the order of nodes in edges matters. For the remaining models, however, this is not the case.

Main results

For every $c>0$, and for every one of the six models described in Section 2, there exists (model dependent) $H(c)$ such that

w.h.p. Moreover, $H(c)$ is a Lipschitz continuous function with Lipschitz constant $1$. It is a nondecreasing function of $c$ for MAX-CUT, coloring, K-SAT and NAE-K-SAT models, and is a nonincreasing function of $c$ for the independent set model.

Also for every $c>0$ there exists $p(c)$ such that

for coloring, K-SAT and NAE-K-SAT models.

As a corollary, one obtains the following variant of the satisfiability conjecture.

For coloring, K-SAT and NAE-K-SAT models, there exists a critical value $c^{*}_{H}$ such that $H(c)=c$ when $c<c^{*}_{H}$ and $H(c)<c$ when $c>c^{*}_{H}$. Similarly, there exists $c^{*}_{p}$, such that $p(c)=0$ when $c<c^{*}_{p}$ and $p(c)<0$ when $c>c^{*}_{p}$.

Namely, there exists a threshold value $c^{*}$ such that if $c<c^{*}$ there exists w.h.p. as $N\rightarrow\infty$ a nearly satisfiable assignment [assignment satisfying all but $o(N)$ clauses], and if $c>c^{*}$, then w.h.p. as $N\rightarrow\infty$, every assignment violates linearly in $N$ many clauses. The interpretation for coloring is similar. The result above was established earlier by the second author for randomly generated linear programming problems, using the local weak convergence and martingale techniques gamarnikLSAT . It would be interesting to see if the same result is obtainable using the interpolation method.

Can one use Corollary 1 to prove the satisfiability conjecture in the precise sense? The answer would be affirmative, provided that a stronger version of Friedgut’s result Friedgut on the sharp thresholds for satisfiability properties holds.

For the coloring, K-SAT and NAE-K-SAT models there exists a sequence $M^{*}_{N}$ such that for every $\varepsilon>0$ there exists $\gamma=\gamma(\varepsilon)$ such that $\lim_{N\rightarrow\infty}p(N,\lfloor(1-\varepsilon)M^{*}_{N}\rfloor)=1$ and $p(N,\lfloor(1+\varepsilon)M^{*}_{N}\rfloor)=O(\exp(-\gamma N))$, for all $N$.

In contrast, Friedgut’s sharp phase transition result Friedgut replaces the second part of this conjecture with (a weaker) statement $\lim_{N\rightarrow\infty}p(N,\lfloor(1+\varepsilon)M^{*}_{N}\rfloor)=0$. Thus, we conjecture that beyond the phase transition region $M^{*}_{N}$, not only is the model not satisfiable w.h.p., but in fact the probability of satisfiability converges to zero exponentially fast. The import of this (admittedly bold) statement is as follows:

Conjecture 1 together with Theorem 1 implies the satisfiability conjecture. Indeed, it suffices to show that $c_{h}^{*}$ is the satisfiability threshold. We already know that for every $\varepsilon>0$, $p(N,\lfloor(1+\varepsilon)c^{*}_{h}N)\rightarrow 0$, since $H((1+\varepsilon)c_{h}^{*})<(1+\varepsilon)c_{h}^{*}$. Now, for the other part it suffices to show that $\liminf_{N}M_{N}^{*}/N\rightarrow c_{h}^{*}$. Suppose not, namely there exists $\varepsilon>0$ and a sequence $N_{k}$ such that $(M_{N_{k}}^{*}/N_{k})+\varepsilon<c_{h}^{*}$ for all $k$. Then $(M_{N_{k}}^{*}/N_{k})+\varepsilon/2<c_{h}^{*}-\varepsilon/2$, implying that

Let us now state our results for the existence of the scaling limit for the log-partition functions.

For every $c>0,1\leq\lambda<\infty$, and for every one of the models described in Section 2, there exists (model dependent) $z(c)$ such that

w.h.p., where $z(c)$ is a Lipschitz continuous function of $c$. Moreover, $z(c)$ is nondecreasing for MAX-CUT, coloring, K-SAT and NAE-K-SAT models, and is a nonincreasing function of $c$ for the independent set model.

We now turn to our results on random regular graphs.

Note, that in the statement of the theorem we take limits along subsequence $N$ such that $NrK^{-1}$ is an integer, so that the resulting random hypergraph is well-defined. Unlike the case of Erdös–Rényi graph, we were unable to prove the existence of the large deviation rate

for the coloring, K-SAT and NAE-K-SAT problems and leave those as open questions.

Finally, we state our results for the log-partition function limits for random regular graphs.

Proofs: Optimization problems in Erdös–Rényi graphs

where we can take $L=1$ for all the models except Ising, and we can take $L=\beta$ for the Ising model. This follows from the fact that adding (deleting) an edge to (from) a graph changes the value of $H$ by at most $1$ for all models except for the Ising model, where the constant is $\beta$.

Our main technical result leading to the proof of Theorem 1 is as follows.

For every $1\leq N_{1},N_{2}\leq N-1$ such that $N_{1}+N_{2}=N$, and all models

where $\mathcal{M}_{1}\stackrel{{\scriptstyle d}}{{=}}\operatorname{Bi}(\lfloor cN\rfloor,N_{1}/N)$ and $\mathcal{M}_{2}\triangleq\lfloor cN\rfloor-\mathcal{M}_{1}\stackrel{{\scriptstyle d}}{{=}}\operatorname{Bi}(\lfloor cN\rfloor,N_{2}/N)$.

Additionally, for the same choice of $\mathcal{M}_{j}$ as above and for coloring, K-SAT and NAE-K-SAT models,

when $M_{1}\leq M_{2}$; adding hyperedges can only increase the objective value since the edge potentials are nonnegative. For the Independent set problem on the contrary

holds. The Lipschitz continuity follows from (6) which implies

with $L=\beta$ for the Ising model, and $L=1$ for the remaining models. This concludes the proof of (1).

We now turn to the proof of (2) and use (8) for this goal. Our main goal is establishing the following superadditivity property:

There exist $0<\alpha<1$ such that for all $N_{1},N_{2}$ such that $N=N_{1}+N_{2}$

Proof of Proposition 1 Fix any $1/2<\nu<1$. First we assume $N_{1}\leq N^{\nu}$. Let $\mathcal{M}_{j}$ be as in Theorem 5. We have

From our assumption $N_{1}\leq N^{\nu}$ it follows that

Now we claim the following crude bound for every deterministic $m$ and every one of the three models under the consideration.

The proof for the NAE-K-SAT is similar. For the coloring problem observe that this conditional probability is at least $(1-1/N)(2(N-1)/N^{2})=O(1/N)$ since with probability $1-1/N$ the new edge chooses different nodes, and with probability at least $2(N-1)/N^{2}$ the new edge does not violate a given coloring (with equality achieved only when $q=2$, and two coloring classes having cardinalities $1$ and $N-1$). The claim follows.

Now since $\lfloor cN\rfloor-\lfloor cN_{2}\rfloor\leq\lfloor cN_{1}\rfloor+1$, the claim implies

After taking logarithm of both sides we obtain (9) from (8).

The case $N_{2}\leq N^{\nu}$ is considered similarly. We now turn to a more difficult case $N_{j}>N^{\nu},j=1,2$.

First we state the following lemma (proved in Appendix A) for the three models of interest (coloring, K-SAT, NAE-K-SAT).

The following holds for coloring, K-SAT, NAE-K-SAT models for all $N,M,m$ and $0<\delta<1/2$:

where $H(\delta)=-\delta\log\delta-(1-\delta)\log(1-\delta)$ is the entropy function.

We now prove (2). Fix $h\in(1/2,\nu)$. We have from (8),

Note that $cN_{1}-N^{h}\leq m_{1}\leq cN_{1}+N^{h}$ implies $cN_{2}-N^{h}-1\leq m_{2}\leq cN_{2}+N^{h}$. Applying Lemma 1 we further obtain for the relevant range of $m_{j}$ that

where we have used a simple bound $p(N_{j},\lfloor cN_{j}\rfloor)\geq(1-1/q)^{cN_{j}}$. Now let us take $\delta$ so that

Then using the assumptions $N_{j}\geq N^{\nu}$ and $h<\nu$ we obtain

Since $\mathcal{M}_{1}\stackrel{{\scriptstyle d}}{{=}}\operatorname{Bi}(\lfloor cN\rfloor,N_{1}/N)$ and $h>1/2$, then

where the last identity is of course a very crude estimate. Combining, we obtain

The claim of Proposition 1 is established.

Part (2) of Theorem 1 then follows from this proposition and Proposition 5 from Appendix B.

For every $r=1,\ldots,\lfloor cN\rfloor$,

Also for coloring, K-SAT and NAE-K-SAT models,

We now prove properties (12) and (4) for each of the six models.

Using ${N_{1}\over N}({|O_{j}^{*}\cap[N_{1}]|\over N_{1}})^{2}+{N_{2}\over N}({|O_{j}^{*}\cap[N_{2}]|\over N_{2}})^{2}\geq({|O_{j}^{*}|\over N})^{2}$ we obtain (12).

Given an edge $e=(i,k)$, the following holds:

By a similar argument and again using Lemma 2 we obtain

Recall, however, that $H_{m+1}-H_{m}<0,m\leq M-1$ and $H-H_{M}-2\beta\leq 0$. Again using the convexity of the $g(x)=x^{2}$ function, we obtain the claim.

Relation (4) then again follows from convexity.

Using the convexity of the function $x^{K}$ on $x\in[0,\infty)$, we obtain the result.

We have established (12) and (4). With this, the proof of Proposition 2 is complete.

Finally we give a simple proof of Corollary 1.

Proof of Corollary 1 Define $c^{*}_{H}=\sup\{c\geq 0\dvtx H(c)=c\}$. It suffices to show that $H(c)<c$ for all $c>c^{*}_{H}$. For every $\delta>0$ we can find $c_{0}\in(c,c+\delta)$ such that $H(c_{0})<c_{0}$. By Lipshitz continuity result of Theorem 1 it follows that $H(c)\leq H(c_{0})+(c-c_{0})<c$ for all $c>c_{0}$, and the assertion is established.

Proofs: Log-partition function in Erdös–Rényi graphs

where our claim was used in the second inequality. Assertion (14) then follows after taking logarithms.

The analogue of Theorem 5 is the following result.

For every $1\leq N_{1},N_{2}\leq N-1$ such that $N_{1}+N_{2}=N$ and every $\lambda>1$,

where $\mathcal{M}_{1}\stackrel{{\scriptstyle d}}{{=}}\operatorname{Bi}(\lfloor cN\rfloor,N_{1}/N)$ and $\mathcal{M}_{2}\triangleq\lfloor cN\rfloor-\mathcal{M}_{1}\stackrel{{\scriptstyle d}}{{=}}\operatorname{Bi}(\lfloor cN\rfloor,N_{1}/N)$.

As before, we do not have independence of $\mathcal{M}_{j},j=1,2$. Let us first show how this result implies Theorem 2. {pf*}Proof of Theorem 2 Since $\mathcal{M}_{j}$ have binomial distribution, using observation (14) and Theorem 6, we obtain

Now we use Proposition 5 in Appendix B for the case $\alpha=1/2$ to conclude that the limit

For every $r=1,\ldots,\lfloor cN\rfloor$,

The proof of (16) is done on a case-by-case basis, and it is very similar to the proof of (12).

Again using the convexity of $f(x)=x^{2}$ we obtain

Since $\lambda>1$ we have $0<(1-\lambda^{-1})\mu_{0}(x_{i}=x_{j})<1$ (this is where the condition $\lambda>1$ is used), implying

Using the convexity of the function $f(x)=x^{2}$, we obtain (16).

Ising, coloring, K-SAT and NAE-K-SAT. The proofs of the remaining cases are obtained similarly and are omitted. The condition $\lambda>1$ is used to assert positivity of $1-\lambda^{-1}$ in the logarithm expansion.

Proofs: Random regular graphs

Our result leading to the proof of Theorem 3 is as follows.

For every $N_{1},N_{2}$ such that $N=N_{1}+N_{2}$ and $N_{1}r/K,N_{2}r/K$ are integers,

Thus we have defined an interpolation procedure for $t\leq T_{1,K-1}$. Assuming that the procedure did not fail for $t\leq T_{1,K-1}$, we now define it for $T_{1,K-1}+1\leq t\leq T_{2,K-2}$ analogously: we delete a randomly chosen hyperedge connecting two parts such that the hyperedge has $2$ nodes in part $j=1$, and $K-2$ nodes in part $j=2$. Then we add a hyperedge uniformly at random to part $j=1,2$ to connect $K$ isolated nodes with probability $2/K$ and $(K-2)/K$, respectively. The failure of the interpolation is defined similarly as above. We continue this for all partitions $(K_{1},K_{2})$ until $(K-1,1)$, inclusive. For the $(K_{1},K_{2})$ phase of the interpolation procedure the probabilities are $K_{1}/K$ and $K_{2}/K$, respectively.

The claim is trivial when $T_{0}+1\leq t$, since the graph remains the same. Notice also that

since the two graphs are identical, and thus the statement of the proposition holds.

Now we will condition on the event $\mathcal{I}_{t}$. We now establish a stronger result. Namely,

We now conduct model-dependent, case-by-case analysis.

Therefore, the value of $H$ decreases by one with probability

and stays the same with the remaining probability. Using the inequality $(1/2)(x^{2}+y^{2})\geq xy$, we obtain (19).

Applying Young’s inequality, namely that $ab\leq pa^{1/p}+qb^{1/q}$ for every $a,b\geq 0$, $p+q=1,p,q>0$, with the choice $p=K_{1}/K,q=K_{2}/K$,

and canceling $1/2^{K}$ on both sides, we obtain the result.

Our next step is to control the error term in (18).

The interpolation procedure succeeds (event $\mathcal{I}$ holds) with probability at least $1-O(N\exp(-N^{\delta}))$ for some $\delta>0$. Additionally,

Now ignoring term $K$ in the expression $(1/2)N_{j}/N^{1/3}+K-N_{j}^{3/5}$ and using $T_{0}\leq\min_{j}(N_{j}r)$, we obtain that with probability $1-O(N\exp(-N^{\delta}))$, the expression inside the expectation on the left-hand side of (22) is at most

The numerator is at most $N^{2/5}r$. Also the assumption $\min N_{j}\geq 40N^{5/6}$ implies that the denominator is at least $1$. We conclude that the expression inside the expectation is at most $N^{2/5}r$ with probability at least $1-O(N\exp(-N^{\delta}))$. Since we also have $T_{0}\leq Nr$ w.p.1, then using a very crude estimate $O(N\exp(-N^{\delta}))=O(N^{-3/5})$, and $NN^{-3/5}=N^{2/5}$, we obtain the required result.

As a corollary of Proposition 4 and Lemma 3 we obtain

for the case $\min_{j}N_{j}\geq 40N^{5/6}$. This completes the proof of Theorem 7.

Proof of Theorem 3 The existence of the limit

follows immediately from Theorem 7 and Proposition 5 from Appendix B. Then the convergence w.h.p.

follows once again using standard concentration results JansonBook .

The proof of Theorem 4 uses the same interpolation as the one above, and the proof itself mimics the one for Theorem 2. For this reason, we omit the details.

Appendix A Proof of Lemma 1

In other words, if the current graph is satisfiable, the new graph obtained by adding a random hyperedge remains satisfiable with probability at least $\omega$. Indeed, for example, for the case of K-SAT, if the instance is satisfiable and $x$ is a satisfying assignment, the added edge remains consistent with $x$ with probability at least $\omega\triangleq 1-1/2^{K}>1/2$. For the case of NAE-K-SAT it is $\omega=1-1/2^{K-1}\geq 1/2$. We obtain that for every positive $M,m$ and recalling assumption $\delta<1/2$,

using the earlier established claim. Iterating this inequality, we obtain for every $m\geq 1$,

where $\sum_{0\leq j\leq m}\delta^{m}(1-\delta)^{m}\leq 1/(1-\delta)<2$ is used in the last inequality. This completes the proof of the lemma.

Appendix B Modified super-additivity theorem

To keep the proof of our main results self-contained, we state and prove the following proposition, used in proving several of the theorems presented in the earlier sections. However, Béla Bollobás and Zoltan Füredi kindly pointed out to us that the following proposition is a special case of a more general and classical theorem of de Bruijn and Erdös (see Theorem 22 on page 161 in deBE52 ), which uses a weaker assumption on the additive term in the near super-additivity hypothesis; also see deBE51 and the Bollobás–Riordan percolation book BR2006 for more recent applications of this useful tool.

Given $\alpha\in(0,1)$, suppose a nonnegative sequence $a_{N}$, $N\geq 1$ satisfies

for every $N_{1},N_{2}$ s.t. $N=N_{1}+N_{2}$. Then the limit $\lim_{N\to\infty}{a_{N}\over N}$ exists.

It is convenient to define $a_{N}=a_{\lfloor N\rfloor}$ for every real, but not necessarily integer value $N\geq 1$. It is then straightforward to check that property (24) holds when extended to reals as well [thanks to the correction term $O(N^{\alpha})$]. Let

Fix $\varepsilon>0$ and find $k$ such that $1/k<\varepsilon\leq 1/(k-1)$. Find find $N_{0}=N_{0}(\varepsilon)$ such that $N_{0}^{-1}a_{N_{0}}\geq a^{*}-\varepsilon$, $k^{\alpha}N_{0}^{\alpha-1}<\varepsilon$. Clearly, such $N_{0}$ exists. Consider any $N\geq kN_{0}$. Find $r$ such that $kN_{0}2^{r}\leq N\leq kN_{0}2^{r+1}$. Applying (24) iteratively with $N_{1}=N_{2}=N/2$ we obtain

Now let us find $i$ such that $(k+i)N_{0}\leq N/2^{r}\leq(k+i+1)N_{0}$. Note $i\leq k$. Again using (24) successively with $N_{0}$ for $N_{1}$ and $N/2^{r},(N/2^{r})-N_{0},(N/2^{r})-2N_{0},\ldots$ for $N_{2}$, we obtain

where $1/k<\varepsilon$ is used in the last inequality. Now

again by the choice of $N_{0}$. We have obtained

for all $N\geq N_{0}k$. Since $\varepsilon$ was arbitrary the proof is complete.

Acknowledgments

The authors are grateful for the insightful discussions with Silvio Franz, Andrea Montanari, Lenka Zdeborová, Florant Krzakala, Jeff Kahn and James Martin. The authors thank Zoltan Füredi and Béla Bollobás for bringing the deBruijn–Erdös theorem and other relevant literature, mentioned in Appendix B, to the authors’ attention. The authors are especially thankful to anonymous referees for helpful technical comments and notation suggestions. Authors also thank Microsoft Research New England for the hospitality and the inspiring atmosphere, in which this work began.

References