On phase transition in the hard-core model on ${\bf Z}^d$

Introduction

The “hard-core model” is a simple mathematical model of a gas with particles of non-negligible size. The vertices (“sites”) of a graph are regarded as positions, each of which can be occupied by a particle, subject to the rule that two neighboring sites cannot both be occupied (particles cannot overlap).

We need a few definitions, but aim to be brief. For good introductions to the hard-core model see , . See also for more general background, and e.g. or for graph theory basics. A few conventions are mentioned at the end of this section.

Write ${\cal I}(\Sigma)$ for the collection of independent sets (sets of vertices spanning no edges) of graph $\Sigma$.

For $\Sigma$ finite and $\lambda>0$, the hard-core measure with activity (or fugacity) $\lambda$ on ${\cal I}={\cal I}(\Sigma)$ (or “on $\Sigma$”) is given by

where $Z$ is the appropriate normalizing constant (partition function), $Z=\sum\{\lambda^{|I^{\prime}|}:I^{\prime}\in{\cal I}\}$. (The more usual etiquette here considers probability measures on $\{0,1\}^{V(\Sigma)}$ supported on indicators of independent sets; but the present usage is convenient for us, and we adhere to it throughout.)

In particular $\lambda=1$ gives uniform distribution. One may also assign different activities $\lambda_{v}$ to the different vertices $v$ and take $\mu(I)$ proportional to $\prod_{v\in I}\lambda_{v}$, but we will not do so here; again see , , and also e.g. , , for some combinatorial applications.

For infinite $\Sigma$ a measure $\mu$ on ${\cal I}(\Sigma)$ is hard-core with activity $\lambda$ if, for ${\bf I}$ chosen according to $\mu$ and for each finite $W\subset V=V(\Sigma)$, the conditional distribution of ${\bf I}\cap W$ given ${\bf I}\cap(V\setminus W)$ is $\mu$-a.s. the hard-core measure with activity $\lambda$ on the independent sets of $\{w\in W:w\not\sim{\bf I}\cap(V\setminus W)\}$ (the vertices that can still be in ${\bf I}$ given ${\bf I}\cap(V\setminus W)$). General considerations (see ) imply that there is always at least one such $\mu$; if there is more than one, the model is said to have a phase transition.

The canonical (and by far most studied) case of the hard-core model is that of (the usual nearest neighbor graph on) ${\bf Z}^{d}$. Here the seminal result is due to Dobrushin , who proved that there is a phase transition for sufficiently large $\lambda$, depending on $d$. (Dobrushin’s result was rediscovered by Louth in the context of communications networks.)

The $\lambda$ required in is larger than one would expect, No explicit bound is given in , but several colleagues report that Dobrushin’s argument works for $\lambda>C^{d}$ for a suitable constant $C$. and attempted improvements have been the subject of considerable effort—if not publication—in both the statistical mechanics and discrete mathematics communities in recent years.

Even the fact that the required $\lambda$ increases with $d$ is a little strange, since one expects that as $d$ grows phase transition should get “easier,” in the sense that for a given $\lambda$, phase transition in dimension $d$ should imply phase transition in all higher dimensions; but this remains open.

Also open is the existence of a “critical” activity, $\lambda_{c}(d)$, such that one has phase transition for $\lambda>\lambda_{c}(d)$ but not for $\lambda<\lambda_{c}(d)$. While this seems certain to be true for ${\bf Z}^{d}$, a cautionary note is sounded in , where it is shown that there are graphs (even trees) for which there is no such critical activity.

As a temporary substitute we may define $\lambda(d)$ to be the supremum of those $\lambda$ for which the hard-core model with activity $\lambda$ on ${\bf Z}^{d}$ does not have a phase transition.

So Dobrushin at least tells us that $\lambda(d)<\infty$, while “easier as dimension grows” would imply $\lambda(d)<O(1)$. A particular question that has received much of the attention devoted to this problem is whether $\lambda(d)\leq 1$ for large $d$. But in fact it has been generally believed (despite some early guesses to the contrary) that $\lambda(d)$ tends to zero as $d$ grows; this is what we prove:

The bound here is undoubtedly not best possible; $O(\log d/d)$ and $O(1/d)$ are natural guesses at the true value of $\lambda(d)$.

We assume henceforth that $d$ is large enough to support our various assertions.

The problem of showing existence of a phase transition may be finitized as follows. Let $\Lambda=\Lambda_{M}={\bf Z}^{d}\cap[-M,M]^{d}={\cal O}\cup{\cal E}$ with ${\cal O}$ and ${\cal E}$ the sets of odd and even vertices (defined in the natural way: $x\in{\bf Z}^{d}$ is odd if $\sum x_{i}$ is odd); let $\mu_{M}$ be the hard-core measure with activity $\lambda$ on $\Lambda$ (meaning, of course, on the subgraph of ${\bf Z}^{d}$ induced by $\Lambda$); and (with ${\bf I}$ chosen according to $\mu_{M}$) let $\mu_{M}^{e}$ be $\mu_{M}$ conditioned on the event $\{{\bf I}\supseteq\partial^{\star}\Lambda\cap{\cal E}\}$, where $\partial^{\star}\Lambda:=[-M,M]^{d}\setminus[-(M-1),M-1]^{d}$, and define $\mu_{M}^{o}$ similarly.

In it is shown (inter alia) that the sequences $\{\mu_{M}^{e}\}$ and $\{\mu_{M}^{o}\}$ converge to weak limits, called $\mu^{e}$ and $\mu^{o}$, and that there is a phase transition iff these limits are different. (This is mainly based on the FKG Inequality, and applies to general bipartite graphs $\Sigma$, provided we allow $\{\Lambda_{M}\}$ to be an arbitrary nested sequence with $\cup\Lambda_{M}=V(\Sigma)$.)

Thus it is natural to try to prove phase transition by exhibiting some statistic distinguishing $\mu^{e}$ from $\mu^{o}$. We will show $\mu^{e}(\underline{0}\in{\bf I})\neq\mu^{o}(\underline{0}\in{\bf I})$, i.e.

(Of course we are only using the trivial direction of “phase transition iff $\mu^{e}\neq\mu^{o}$.” It is not hard to show that (1), too, is equivalent to phase transition.)

To establish (1) (assuming at least $\lambda=\Omega(1/d)$, which is easily seen to be necessary for phase transition) it is in turn enough to show that for $v_{0}\in\Lambda$,

so that $\mu^{e}(\underline{0}\in{\bf I})=(1-o(1))\lambda/(1+\lambda)$, whereas $\mu^{o}(\underline{0}\in{\bf I})=o(1/d)$.

So in particular the next theorem, whose proof is the main business of this paper, contains Theorem 1.1.

M arbitrary, and $v_{0}$ an odd vertex of $\Lambda_{M}$,

The same result holds if we reverse the roles of even and odd.

so that (3) actually gives the asymptotics of $\log\mu_{M}^{e}(v_{0}\in{\bf I})$.

The proof of Theorem 1.2 is a sort of “Peierls argument” (see e.g. ): we try to associate with each $I\in{\cal J}$ containing $v_{0}$ a “contour”—some kind of membrane separating the outer even region from an inner odd region containing $v_{0}$—and then use this to map $I$ to a large set of $J$’s, also from ${\cal J}$ but not containing $v_{0}$, each obtained from $I$ by some modification of the inner region.

This is no surprise: almost every attempt at settling this problem that we’re aware of has attacked it more or less along these lines. (The one exception is the entropy approach of , which for now seems unlikely to get us to anything like what’s proved here.)

The main difficulty in all these attempts has been getting some kind of control over the set of possible “contours.” Much of the inspiration for our approach to this problem was provided by the beautiful ideas of A. Sapozhenko , which he used to give, for example, relatively simple derivations of Korshunov’s description of the asymptotics for Dedekind’s Problem (in ), and, in , of the asymptotics for the number of independent sets (“codes of distance 2”) in the Hamming cube $\{0,1\}^{n}$ originally established in .

Some of our tools also come from : Lemma 2.17 is an improved version of one of Sapozhenko’s arguments, and our uses of Lemmas 2.1-2.3 are similar to his.

The rest of the paper is devoted to the proof of Theorem 1.2. Unfortunately, saying anything even mildly intelligible about the argument turns out to be awkward without some preliminaries, so we will wait: see the end of Section 2.2 and most of Section 2.6. (Section 2.2 reformulates slightly and says what we will actually prove.)

For a graph on vertex set $V$, we use $\nabla(W)$ for the set of edges having exactly one end in $W\subseteq V$ and $\nabla(U,W)$ for the set of edges having one end in $U$ and the other in $W$.

The neighborhood of (i.e. set of vertices adjacent to) $v$ is $N(v)$; $N(W)=\cup\{N(v):v\in W\}$; and $\partial W=N(W)\setminus W$. We use $d(\cdot)$ for degree—$d(v)=|N(v)|$ and $d_{W}(v)=|N(v)\cap W|$—and ${\rm dist}(\cdot,\cdot)$ for distance.

One common abuse: we often fail to distinguish between a graph and its set of vertices, so for instance might use “component” where we should really say “set of vertices of a component.”

When the difference makes no difference, we pretend that all large numbers are integers. All constants implied by the notations $O(\cdot)$, $\Omega(\cdot)$ are absolute; that is, they do not depend on $d$.

Proof of Theorem 1.2

Here we collect what we will need in the way of known results.

In any graph with all degrees at most $D$, the number of connected, induced subgraphs of order $n$ containing a fixed vertex $x_{0}$ is at most $(eD)^{n}$.

This follows from the well-known fact (e.g. [15, p.396, Ex.11]) that the infinite $D$-branching rooted tree contains precisely $\frac{1}{(D-1)n+1}{Dn\choose n}$ rooted subtrees of size $n$.

The next lemma is a special case of a fundamental result due to Lovász and Stein (see also ). For a bigraph $\Sigma$ with bipartition $X\cup Y$, say $Y^{\prime}\subseteq Y$ covers $X$ if each $x\in X$ has a neighbor in $Y^{\prime}$.

If $\Sigma$ as above satisfies $d(x)\geq a~\forall x\in X$ and $d(y)\leq b~\forall y\in Y$, then $X$ is covered by some $Y^{\prime}\subseteq Y$ of size at most $(|Y|/a)(1+\ln b)$.

Call a set $T$ of vertices of a graph c-clustered if for any $x,y\in T$ there are vertices $x=x_{0},x_{1},\ldots,x_{k}=y$ with ${\rm dist}(x_{i-1},x_{i})\leq c$ for all $i$. The next lemma is from (see Lemma 2.1); the interested reader should have no difficulty supplying a proof.

If $\Sigma$ is a graph on V and $S,T\subseteq V$ satisfy

(ii) ${\rm dist}(x,T)\leq b~\forall x\in S$ and ${\rm dist}(y,S)\leq b~\forall y\in T$,

Let $C$ be a subset of ${\bf Z}^{d}$ with

This is an immediate consequence of a corresponding inequality for the torus $({\bf Z}/k{\bf Z})^{d}$, given by Bollobás and Leader in [3, Cor. 5]. The case $\alpha=0$ was proved by Wang and Wang .

2 To prove

We assume henceforth that $\lambda$ satisfies (2). We prove only the first part of Theorem 1.2 ((3) for odd $v_{0}$); switching “even” and “odd” throughout the argument gives the proof of the second part.

It will be convenient to replace the box $\Lambda_{M}$ by the discrete torus $\Gamma=\Gamma_{M}$ obtained from $\Lambda_{M}$ by setting $M=-M$ and identifying vertices accordingly. Following our favorite abuse, we regard $\Gamma$ as either a graph or a set of vertices as convenient.

We then use $\Delta$ for the image of $\partial^{\star}\Lambda_{M}$ under the natural projection $\Lambda_{M}\mapsto\Gamma$, and continue to write $\underline{0}$ for the image of $\underline{0}$ in $\Gamma$, and to use ${\cal O}$ and ${\cal E}$ for the sets of odd and even vertices of $\Gamma$.

Having done this, we replace $\partial^{\star}\Lambda_{M}$ by $\Delta$ in the definition of ${\cal J}$ ({\cal J}=\{I\subseteq\Gamma:\mbox{I$independent,$\Delta\cap{\cal E}\subseteq I}\}), define $\mu_{M}^{e}$, $\mu_{M}^{o}$ as before, and simply regard Theorem 1.2 as referring to $\Gamma$, a change which clearly does not affect its meaning.

We will show a bit more than (3): for $I\in{\cal J}$, let $Z=Z(I)$ be the component of $\Gamma-(I\cap{\cal O})$ containing $\Delta$; then

Let ${\cal J}_{0}=\{I\in{\cal J}:v_{0}\not\in Z(I)\}$, and write $w(I)$ for $\lambda^{|I|}$. We prove (4) by producing a “flow” $\nu:{\cal J}_{0}\times{\cal J}\rightarrow$ satisfying

Throughout our discussion we fix $v_{0}$ and use $I$ for members of ${\cal J}_{0}$ and $J$ for general members of ${\cal J}$.

The definition of $\nu(I,\cdot)$ will depend on a pair $(G,A)=(G(I),A(I))\in 2^{\cal E}\times 2^{\cal O}$ associated with $I$. The construction and salient properties of the pair are given in Sections 2.3 and 2.4, but it will not be until Section 2.11 that we are able to specify $\nu$. First steps toward this specification are taken in Section 2.5, which finally puts us in a position—in Section 2.6—to give some clue as to how the main part of the argument will proceed.

3 “Contours”

For a set $P$ of vertices (in any graph) we use $\partial^{\star}P$ for the internal boundary of $P$:

The following observation is used several times, so we record it as a lemma; its easy proof is left to the reader.

Let $\Sigma$ be a graph, $S\subseteq V(\Sigma)$, and $T$ (the vertex set of) some component of $\Sigma-(S\setminus\partial^{\star}S)$. Then $\partial^{\star}T\subseteq\partial^{\star}S$.

Let $I\in{\cal J}_{0}$, $Z=Z(I)$ be as in Section 2.2, and set $Z_{0}=\partial^{\star}Z$. By the definition of $Z$, it is clear that $Z_{0}\subset{\cal E}$ and $Z_{0}\cap I=\emptyset$. Let $W^{\prime}$ be the component of $v_{0}$ in the graph $\Gamma-(Z\setminus Z_{0})$. By Lemma 2.5, $\partial^{\star}W^{\prime}\subseteq W^{\prime}\cap Z_{0}\subseteq{\cal E}$.

Let $W^{\prime\prime}=W^{\prime}\cup\{x\in{\cal O}|N(x)\subseteq W^{\prime}\}$. This is clearly connected, with $\partial^{\star}W^{\prime\prime}\subseteq\partial^{\star}W^{\prime}$.

Now consider $\Gamma-(W^{\prime\prime}\setminus\partial^{\star}W^{\prime\prime})$. This breaks into a number of components, one of which, $C$ say, contains $\Delta$. Again using Lemma 2.5, we have $\partial^{\star}C\subseteq C\cap\partial^{\star}W^{\prime\prime}.$ Finally, set $W=\Gamma\setminus(C\setminus\partial^{\star}C)$, $G=W\cap{\cal E}$, $A=W\cap{\cal O}$, and $G_{0}=\partial^{\star}W$.

The next proposition collects relevant properties of these objects. Once we have these properties, we will not be concerned with how $G,A$ etc. were derived from $I$.

Proof. Both (7) and the connectivity of $C$ are immediate. To see that $W$ is connected, notice that each component of $\Gamma-(W^{\prime\prime}\setminus\partial^{\star}W^{\prime\prime})$ must meet $\partial^{\star}W^{\prime\prime}$ (or it would be a component of the connected graph $\Gamma$). Thus $W$ is the union of the connected set $W^{\prime\prime}$ and a number of other connected sets each of which meets $W^{\prime\prime}$, so is itself connected. So we have (8).

For (9): $\partial^{\star}C\subseteq W\cap{\cal E}$ and the connectivity of $C$ give

so $\partial^{\star}C\subseteq\partial^{\star}W$; and Lemma 2.5 and the connectivity of $W$ give the reverse containment.

Connectivity of $W$ and the fact that $G_{0}\subseteq{\cal E}$ give $G=N(A)$. That $A\subseteq\{x\in{\cal O}|N(x)\subseteq G\}$ follows from $G=N(A)$ (or just $\partial^{\star}W\subseteq{\cal E}$). For the reverse containment, notice that $x\not\in W\Rightarrow N(x)\cap W\subseteq G_{0}\subseteq W^{\prime}$, whereas $N(x)\subseteq W^{\prime}$ would imply $x\in W^{\prime\prime}\subseteq W$; so $x\not\in W\Rightarrow N(x)\not\subseteq W$.

For (11) recall that $G_{0}=\partial^{\star}C\subseteq\partial^{\star}W^{\prime\prime}\subseteq\partial^{\star}W^{\prime}\subseteq Z_{0}$ and $Z_{0}\cap I=\emptyset$.

That $N(G_{0})\cap I\subseteq A$ follows from $G_{0}\subseteq\partial^{\star}W^{\prime}$, since $N(\partial^{\star}W^{\prime})\cap I$ is clearly contained in $A$.

Finally, $v\in G_{0}\Rightarrow v\in Z_{0}\Rightarrow v\sim I$, so (13) follows from (12).

4 Topology

The purpose of this section is to prove, for any $I\in{\cal J}_{0}$ and $W$, $G$ etc. produced from $I$ as in Section 2.3,

Our proof of this, which is considerably longer than we would wish and unrelated to the methods in the rest of the paper, might profitably be skipped on a first reading.

Though (14) turns out to follow from the connectivity of $W$ and $C$ (see (8)), we could not see a simple combinatorial proof of the implication, and our argument requires a little topological detour, based on

If $U,V$ are connected subsets of X=\mbox{{\bf R}}^{n} or $S^{n}$, $n>1$, with $U\cup V=X$, $U$ closed and $V$ compact, then $U\cap V$ is connected.

(As usual, $S^{n}$ is the unit sphere \{x\in\mbox{{\bf R}}^{n+1}:\sum x_{i}^{2}=1\}. We also write $B^{n+1}$ for the corresponding unit ball.)

The (presumably well-known) proof of Lemma 2.7 is given at the end of this section.

It will be convenient here to write $\Omega$ for the nearest neighbor graph on ${\bf Z}^{d}$. As usual, $\Omega[S]$ is the subgraph induced by $S$. We will prove (14) in the following more general form.

Let $R\cup B$ be a decomposition of $V(\Omega)$ ($={\bf Z}^{d}$), with both $\Omega[R]$ and $\Omega[B]$ connected and $R$ finite. Suppose $G:=R\cap B$ is contained in ${\cal E}$ and is the internal boundary of each of $R,B$. Then $G$ is 2-clustered.

Remark. We will actually show that $G$ is $2$-clustered in each of $R$ and $B$.

Proof With $\Omega$ embedded in \mbox{{\bf R}}^{d} in the natural way, we extend $R$ and $B$ to closed connected subsets $R^{*}$ and $B^{*}$ of \mbox{{\bf R}}^{d} so that R^{*}\cup B^{*}=\mbox{{\bf R}}^{d} and $G^{*}:=R^{*}\cap B^{*}$ is path-connected. We then derive the $2$-clusteredness of $G$ from the path-connectedness of $G^{*}$.

We view \mbox{{\bf R}}^{d} as the union of ${\bf Z}^{d}$-translates of $^{d}$ (the cells of \mbox{{\bf R}}^{d}), and define $R^{*}$ and $B^{*}$ cell by cell. Within a cell we proceed by dimension, first defining the extensions for $0$-dimensional faces (the vertices of $\Omega$), $1$-dimensional faces (the edges of $\Omega$), and $2$-dimensional faces, and then continuing inductively. (As usual a face of a cell is the intersection of the cell with some supporting hyperplane. Henceforth we use “$k$-face” for “$k$-dimensional face.”) For the inductive step, we need a topological lemma (Lemma 2.11), for the statement of which it’s convenient to introduce two local definitions. Let us say that a subset of a topological space is civilized if it is closed, has only finitely many components, and each of its components is path-connected.

A decomposition $X=R\cup B$ of a topological space $X$, with $R\cap B=G$, is nice if it satisfies:

(ii) each of $R$, $B$, $G$ is civilized; and

(iii) each of $R$, $B$—and so each component of $R$ and $B$—is the closure of the union of finitely many open, path-connected sets.

If $X=R\cup B$ is a nice decomposition, and $R^{\prime}$, $B^{\prime}$ are obtained from $R$, $B$ by adding finitely many points, then we also call the decomposition $X=R^{\prime}\cup B^{\prime}$ nice.

(Of course there is some redundancy in conditions (i)-(iii).)

We say that two nice decompositions $X_{1}=R_{1}\cup B_{1}$ and $X_{2}=R_{2}\cup B_{2}$ are compatible if $R_{1}\cap X_{1}\cap X_{2}=R_{2}\cap X_{1}\cap X_{2}$ and $B_{1}\cap X_{1}\cap X_{2}=B_{2}\cap X_{1}\cap X_{2}$. It’s straightforward to check that nice decompositions of different spaces can be combined if they are compatible:

Suppose $X=X_{1}\cup\cdots\cup X_{m}$ with each $X_{i}$ closed. If $X_{i}=R_{i}\cup B_{i}$ are pairwise compatible, nice decompositions, then $(\cup R_{i})\cup(\cup B_{i})$ is a nice decomposition of $X$.

We now state the topological lemma alluded to above, deferring its proof until after the derivation of Proposition 2.8. (Recall $B^{n+1}$ and $S^{n}$ are the unit ball and sphere in \mbox{{\bf R}}^{n+1}.)

Assume $n>1$. If $R\cup B$ is a nice decomposition of $S^{n}$, then there is a nice decomposition $R^{*}\cup B^{*}$ of $B^{n+1}$, with $R^{*}\cap S^{n}=R$, $B^{*}\cap S^{n}=B$, and such that if $C$ is any component of $R^{*}$ (resp. $B^{*}$, $G^{*}$), then $C\cap S^{n}$ is a component of $R$ (resp. $B$, $G$).

(This is easily seen to fail for $n=1$. It may be worth pointing out that for $R$ and $B$, condition (iii) of Definition 2.9 refers to sets that are open in $S^{n}$; similarly $\partial R$ and $\partial B$ are boundaries relative to $S^{n}$, while $\partial R^{*}$ and $\partial B^{*}$ are boundaries relative to $B^{n+1}$.)

Of course Lemma 2.11 still applies if we replace the $B^{n+1}$ by any of its homeomorphic images (and $S^{n}$ by the corresponding homeomorphic copy); in our case the relevant image will be $^{d}$.

We now fix a cell, and begin defining our extensions. For vertices and edges we do the natural things: $R^{*}\cap V(\Omega)=R$, $B^{*}\cap V(\Omega)=B$; and we put (the interior of) an edge in $R^{*}$ (resp. $B^{*}$) iff both its ends are in $R^{*}$ (resp. $B^{*}$), noting that exactly one of these possibilities occurs, since $\nabla(G,G)=\emptyset$.

Next, we deal with $2$-dimensional faces. If the vertices of such a face are all in $R$ (resp. $B$), then put the interior of the face in $R^{*}$ (resp. $B^{*}$). Otherwise, the face has two opposite corner vertices ($v_{1},v_{3}$, say) in $G$, with one of its remaining two vertices ($v_{2}$) in $R\setminus B$ and the other ($v_{4}$) in $B\setminus R$. Put the interior of the convex hull of $v_{1},v_{2},v_{3}$ in $R^{*}$, the interior of the convex hull of $v_{1},v_{3},v_{4}$ in $B^{*}$, and the interior of the diagonal joining $v_{1}$ and $v_{3}$ in $R^{*}\cap B^{*}$. It is easy to check that these $(R^{*},B^{*})$-decompositions of the $2$-dimensional faces are nice. (It may be worth observing that a 2-dimensional face contained in $R^{*}$ may still have one or two of its vertices in $B^{*}$, and vice versa.)

We now proceed by induction, assuming the decomposition has been defined on faces of dimension less than $k\in\{3,\ldots,d\}$. Each $k$-face $F$ is homeomorphic to $B^{k}$, and is bounded by the union of finitely many $(k-1)$-dimensional faces. The decomposition of each of these bounding faces is nice, and the decompositions on any two faces are compatible (since we are defining the decomposition from lower dimensions up). So, by Lemma 2.10, we have a nice decomposition of the boundary of $F$. We now apply Lemma 2.11 to extend to a nice decomposition of the entire face. Once we have a nice decomposition of each cell, we get the full decomposition \mbox{{\bf R}}^{d}=R^{*}\cup B^{*} by combining the decompositions of the cells, again appealing to Lemma 2.10 for “nice.” (For formal applicability of the lemma, we can use a single $X_{i}=B_{i}$ for the union of all cells not meeting $R$.)

It is clear from the construction that $R^{*}$ and $B^{*}$ are closed, $R^{*}$ is bounded, and R^{*}\cup B^{*}=\mbox{{\bf R}}^{d}. To see that $R^{*}$ is connected, notice that by construction, any component of $R^{*}$ contains an edge of $\Omega[R]$, and that every edge of $\Omega[R]$ is contained in a component of $R^{*}$; connectivity of $R^{*}$ then follows from connectivity of $\Omega[R]$. The same argument shows that $B^{*}$ is connected.

Lemma 2.7 now shows that $G^{*}$ is connected, which, since $G^{*}$ is also civilized (since $R^{*}\cup B^{*}$ is nice), implies that it is actually path-connected.

It remains to show that path-connectedness of $G^{*}$ implies 2-clusteredness of $G$. It is enough to show that for each pair of vertices $u,v\in G$, there is a path connecting them in $G^{*}$ which is supported entirely on the $2$-dimensional faces of \mbox{{\bf R}}^{d}; for, by the construction of $R^{*}$ and $B^{*}$, such a path is supported on diagonals (of $2$-dimensional faces) connecting pairs of vertices from $G$, and such diagonals correspond to steps of length $2$ in $\Omega$. (This also justifies the remark following Proposition 2.8.)

So, consider a $(u,v)$-path $P$ in $G^{*}$ given by the continuous function f:\rightarrow\mbox{{\bf R}}^{d}. If $P$ is supported on $2$-dimensional faces of \mbox{{\bf R}}^{d}, then we are done. Otherwise, let $k>2$ be the maximum dimension of a face whose interior meets $P$. It’s enough to show that we can replace $P$ by a path meeting the interiors of fewer $k$-faces than $P$ and no faces of dimension more than $k$.

To do this, choose a $k$-face $F$ and component $C$ of $G^{*}\cap F$ with $C\cap F^{0}\cap P\neq\emptyset$ (where $F^{0}$ is the interior of $F$). Let $p=\inf\{x\in:f(x)\in C\cap F^{0}\}$ and $q=\sup\{x\in:f(x)\in C\cap F^{0}\}$. Then $f(p),f(q)\in C\cap\partial F$, which, by construction, is path-connected. So we may replace $f([p,q])$ in $P$ by a path contained in $\partial F$.

To avoid confusion, we now write $\partial X$, $\partial\hskip 0.72229pt^{\prime}X$ and $\partial\hskip 0.72229pt^{\prime\prime}X$ for the boundaries of $X$ relative to, respectively, \mbox{{\bf R}}^{n+1}, $B^{n+1}$ and $S^{n}$.

We may assume neither $R$ nor $B$ contains isolated points: otherwise we can simply delete such points, produce $R^{*}$ and $B^{*}$ for the resulting “reduced” $R$ and $B$, and then add the deleted points of $R$ ($B$) to $R^{*}$ ($B^{*}$).

We use $(R,B)$-component to mean a component of either $R$ or $B$, and proceed by induction on the number of ($R$,$B$)-components in the decomposition of $S^{n}$.

If there is exactly one such component (a component of $R$, say), then $R=S^{n}$, and $B=\emptyset$. Setting $R^{*}=B^{n+1}$ and $B^{*}=\emptyset$, we get a nice decomposition of $B^{n+1}$ which satisfies the conditions of the lemma.

Otherwise, there must be at least one ($R$,$B$)-component $T$ for which $S^{n}\setminus T^{0}$ is connected. For suppose $S^{n}\setminus T^{0}$ is disconnected for every ($R$,$B$)-component $T$. Choose an ($R$,$B$)-component $T_{0}$ ($\subseteq R$, say) such that one of the components of $S^{n}\setminus T_{0}^{0}$, $C$ say, contains as few $(R,B)$-components as possible, and let $T_{1}$ be an $(R,B)$-component of $C$ (i.e. contained in $C$, noting that each $(R,B)$-component other than $T_{0}$ is either contained in or disjoint from $C$). Now $S^{n}\setminus C^{0}$ is connected in $S^{n}\setminus T_{1}^{0}$, so $S^{n}\setminus T_{1}^{0}$ (which by assumption is not connected) contains a component whose ($R$,$B$)-components form a proper subset of the ($R$,$B$)-components of $C$, contradicting the choice of $T_{0}$.

Let $T$, then, be an ($R$,$B$)-component with $S^{n}\setminus T^{0}$ connected. We may assume that $T$ is a component of $R$. Applying Lemma 2.7 with $X=S^{n}$, $U=T$ and $V=S^{n}\setminus T^{0}$, we find that $\partial\hskip 0.72229pt^{\prime\prime}T$ is connected, so that $T$ meets exactly one component, say $C$, of $B$ (and $C\supseteq\partial\hskip 0.72229pt^{\prime\prime}T$).

Set $T^{*}=\{\lambda x:x\in T,\lambda\in[1/2,1]\}$. This will be one component of $R^{*}$. It is easy to see that $T^{*}$ is closed and path-connected (so civilized), as is $\partial^{\prime}T^{*}$, and that $T^{*}\cap S^{n}=T$, a component of $R$.

Now let $(T^{*})^{0}$ be the relative interior of $T^{*}$ with respect to $B^{n+1}$ (namely, $(T^{*})^{0}=\{\lambda x:x\in T^{0},\lambda\in(1/2,1]\}$), $P=\partial(B^{n+1}\setminus(T^{*})^{0})$ ($=(S^{n}\setminus T^{0})\cup\partial\hskip 0.72229pt^{\prime}T^{*}$), and $Q=B^{n+1}\setminus(T^{*})^{0}$. Then $(Q,P)$ is (easily seen to be) homeomorphic to $(B^{n+1},S^{n})$.

Let, further, $R_{1}=R\setminus T$, $B_{1}=B\cup\partial\hskip 0.72229pt^{\prime}T^{*}$, and $C_{1}=C\cup\partial\hskip 0.72229pt^{\prime}T^{*}$. Then

(i) the components of $R_{1}$ are precisely the components of $R$ other than $T$,

(ii) the components of $B_{1}$ are $C_{1}$ and the components of $B$ other than $C$,

and it is easy (if tedious) to deduce that $R_{1}\cup B_{1}$ is a nice decomposition of $P$.

Our inductive hypothesis thus gives a nice decomposition $R_{1}^{*}\cup B_{1}^{*}$ of $Q$, and we obtain the desired decomposition, $R^{*}\cup B^{*}$, of $B^{n+1}$ by setting $B^{*}=B_{1}$ and $R^{*}=R_{1}\cup T^{*}$ (again an easy verification using (i) and (ii)).

We first establish a corresponding statement for open sets: if $U,V$ are connected, open subsets of X=\mbox{{\bf R}}^{n} or $S^{n}$, $n>1$, with $U\cup V=X$, then $U\cap V$ is connected.

Proof. We use the Mayer-Vietoris sequence. If $X$ is a topological space, and $U$ and $V$ are open subsets of $X$ whose union is $X$, then this is a long exact sequence of group homomorphisms ending with

where $H_{m}$ is the $m^{th}$ homology group. We apply this with X=\mbox{{\bf R}}^{n} or $S^{n}$. Using the facts that H_{m}(\mbox{{\bf R}}^{n})=0 whenever $m\geq 1$ and that if $O$ is an open subset of \mbox{{\bf R}}^{n} or $S^{n}$, then $H_{0}(O)\cong{\bf Z}$ iff $O$ is connected, this long exact sequence becomes

From the exactness of this sequence, it follows that $H_{0}(U\cap V)\cong{\bf Z}$, so that $U\cap V$ is connected.

Now let $U,V$ be as in the lemma, and for each $\varepsilon>0$, set $U_{\varepsilon}=\{x\in X:d(x,U)<\varepsilon\}$ and $V_{\varepsilon}=\{x\in X:d(x,V)<\varepsilon\}$. These are open, connected sets whose union is $X$, so by the preceding result, $U_{\varepsilon}\cap V_{\varepsilon}$ is connected. Thus $\overline{U_{\varepsilon}\cap V_{\varepsilon}}$ is connected; it is also closed and bounded, so compact. So $U\cap V=\cap_{\varepsilon>0}\overline{U_{\varepsilon}\cap V_{\varepsilon}}$ is the intersection of a nested sequence of compact, connected sets, so is itself connected.

5 Shifts and φj\varphi_{j}

We again fix $I\in{\cal J}_{0}$ and take $W,G,A$ etc. to be as in Section 2.3.

For $j\in\{\pm 1,\ldots,\pm d\}$, define $\sigma_{j}$, the shift in direction $j$, by

where $e_{j}$ is the $j^{th}$ standard basis vector if $j>0$ and $e_{j}=-e_{-j}$ if $j<0$, and set

For each j, the sets $I\setminus W$, $\sigma_{j}(I\cap W)$ and $G_{0}^{j}$ are pairwise disjoint, and their union is an independent set.

Proof. Trivially, $\sigma_{j}(I)\cap I=\emptyset$, so in particular $(I\setminus W)\cap\sigma_{j}(I\cap W)=\emptyset$; $(I\setminus W)\cap G_{0}^{j}=\emptyset$ is trivial (because $G_{0}^{j}\subseteq W$); and $\sigma_{j}(I\cap W)\cap G_{0}^{j}=\emptyset$ follows from the definiton of $G_{0}^{j}$. So the union is disjoint.

Clearly $(I\setminus W)$, $\sigma_{j}(I\cap W)$ and $G_{0}^{j}$ are all independent sets. To show independence of the union, we must show that there are no edges between any two of them. Since $\nabla(I\setminus W,W)=\emptyset$ (by (12)) and $\sigma_{j}(I\cap W)\subseteq W$ (by (11)), we have $\nabla((I\setminus W),(\sigma_{j}(I\cap W)\cup G_{0}^{j}))=\emptyset$.

This leaves $\nabla(\sigma_{j}(I\cap W),G_{0}^{j})$. Suppose, for a contradiction, that $y\in G_{0}^{j}$ and $\sigma_{k}(y)\in\sigma_{j}(I\cap W)$ for some $k$. Then $z:=\sigma_{j}^{-1}(\sigma_{k}(y))\in I\cap W\cap{\cal E}\subset G\setminus G_{0}$ (by (11)), implying $\sigma_{j}^{-1}(y)=\sigma_{k}^{-1}(z)\in A$, contrary to the assumption $y\in G_{0}^{j}$. So $\nabla(\sigma_{j}(I\cap W),G_{0}^{j})=\emptyset$.

Define $\sigma_{j}^{*}(I)=(I\setminus W)\cup\sigma_{j}(I\cap W)$ and

Notice also that we recover $I$ from $j$, $J$ ($\in\varphi_{j}(I)$) and $(G,A)$; namely, if we are given $(G,A)$, $j$, and $J\in\varphi_{j}(I)$, then

6 Conventions and preview

In much of what remains we can ignore $I$ and concentrate on pairs from

Notice that under (10) each of $G$, $A$ determines the other.

If $(G,A)$ is produced from $I$ as in Section 2.3 then we write $(G(I),A(I))$, noting that a given $(G,A)$ may correspond to more than one $I$.

We will always take $W=G\cup A$ and $G_{0}=\partial^{\star}W$ (a subset of ${\cal E}$ because of (10)).

We always take $|G|=g$ and $|A|=a=(1-\delta)g$, and for given $g,\delta$ set

(It’s generally best to think of $\delta$ as small, though it will not always be so.)

As will appear, the quantity that really matters is almost always $\delta g$ ($=|G|-|A|$), and it will be convenient to take, for any $t$,

Though we don’t really need $t$, we use it to emphasize a certain duality: if $(G,A)\in{\cal G}(t)$ in some graph $\Sigma$ satisfying (16), then $({\cal O}\setminus A,{\cal E}\setminus G)$ belongs to the analogue of ${\cal G}(t)$ obtained by reversing the roles of ${\cal O}$ and ${\cal E}$ in $\Sigma$—but of course $g$ and $\delta$, unlike $t$, are not usually preserved by this switch.

Our tasks are to define $\nu$, for which (5) will turn out to be obvious, and establish (6).

We will eventually associate with each $(G,A)$ a particular index $j=j(G,A)$, and set $j(I)=j(G(I),A(I))$. (This is basically a $j$ for which $|G_{0}^{j}|=\log_{2}|\varphi_{j}(I)|$ is large, though there are some additional considerations.) We then define $\varphi(I)=\varphi_{{}_{j(I)}}(I)$ and require

Let us call $I$ small if $|G(I)|\leq d^{3}$ (we could get by with $d^{9/4}$; see (68)), and large otherwise.

For small $I$—an easy case, as we will see in Section 2.13—we simply choose $j=j(I)$ to maximize $|G_{0}^{j}|$ (where $G=G(I)$), so that, since

(Note this satisfies (5). The separate treatment of small $I$ is unnecessary if we only want the phase transition, but is needed for the “correct” bound in (3).)

Most of our work (including everything in Sections 2.4 and 2.8-2.12) is geared to large $I$ (though often valid in general). For most of our discussion we fix $(g,\delta)$, and aim to bound the contribution of ${\cal J}(g,\delta)$ to (6). Of course these contributions must eventually be summed, but this turns out not to add anything significant.

Before beginning in earnest, we pause in Section 2.7 to adapt the isoperimetric Lemma 2.4 to our situation (Lemma 2.13). This is needed especially in Section 2.13, but will also make an appearance in Section 2.8.

In Sections 2.8-2.10 we associate with each relevant $(G,A)$ some $(F,S)\in 2^{\cal E}\times 2^{\cal O}$ which “approximates” $(G,A)$ in an appropriate sense. The definitions of $j(I)$ and $\nu(I,\cdot)$ (in Section 2.11) are then based on our approximation to $(G(I),A(I))$. The main points are: (i) the set of possible approximations is small (Lemma 2.18); and (ii) for a given $J$, $I$’s for which $(G(I),A(I))$ is approximated by a particular $(F,S)$ don’t contribute too much in (6) (see (53)), construction of a $\nu$ achieving this being made possible by the accuracy of our approximations.

The proof that $\nu$ behaves as desired (that is, of (53)) is given in Section 2.12, and Section 2.13 is a mopping up operation, combining what we already know for large $I$’s with the easy analysis for small $I$’s and the isoperimetric information from Lemma 2.13, to finally establish (6).

For whatever $G,A,F,S$ we have under discussion, we set $H={\cal E}\setminus G$, $B={\cal O}\setminus A$, $E={\cal E}\setminus F$, $T={\cal O}\setminus S$, $B_{0}=B\cap N(G)$, $S_{0}=S\cap N(E)$, and $E_{0}=E\cap N(S)$.

From now until Section 2.13 we fix $g,\delta$ and always take $I\in{\cal J}(g,\delta)$ and $(G,A)\in{\cal G}(g,\delta)$. (We will not see $I$ again until Section 2.11.)

7 Isoperimetry

Before continuing, we need to work out what Lemma 2.4 implies in the way of a lower bound on $\delta$ for given $g$.

Suppose $(G,A)\in{\cal G}(g,\delta)$ satisfies

(For the $(G,A)$’s of interest to us, (22) is given by (7).)

Proof. In view of (22), the lemma does not change if we replace the torus $\Gamma$ by the box $\Lambda$.

For the first part of the lemma, the main thing we have to show is

(where $B(r)$, $S(r)$, $b(r)$, $s(r)$ are as defined before Lemma 2.4). Notice that this, combined with Lemma 2.4, implies that for any $C\subset{\bf Z}^{d}$,

Proposition 2.14 is again something for which one would hope to just give a reference; but we could not find one, or even give the short proof that seems called for.

For the proof, we’ll be interested in the average number of nonzero entries in an element of $S(q)$,

This already implies Proposition 2.14 for, say, $r\leq.9d$, since in this case we have

For larger $r$ we will have to work harder. Here we first show, for $q=\beta d$ with $\beta>.9$,

$s(q,t)=|S(q,t)|$, and define $B(q,t)$ and $b(q,t)$ similarly. Then

Set $t_{0}=t_{0}(q)=\lceil(1-1/(4\beta))d\rceil$. Then $t\geq t_{0}$ implies