On the exponential growth rates of lattice animals and interfaces

Abstract

We introduce a formula for translating any upper bound on the percolation threshold of a lattice $G$ into a lower bound on the exponential growth rate of lattice animals $a(G)$ and vice versa. We exploit this in both directions. We obtain the rigorous lower bound ${\dot{p}_c}({\mathbb{Z}}^3)\gt 0.2522$ for 3-dimensional site percolation. We also improve on the best known asymptotic bounds on $a({\mathbb{Z}}^d)$ as $d\to \infty$. Our formula remains valid if instead of lattice animals we enumerate certain subspecies called interfaces. Enumerating interfaces leads to functional duality formulas that are tightly connected to percolation and are not valid for lattice animals, as well as to strict inequalities for the percolation threshold.

Incidentally, we prove that the rate of the exponential decay of the cluster size distribution of Bernoulli percolation is a continuous function of $p\in (0,1)$.

1. Introduction

We improve on the best known asymptotic bounds on the exponential growth rates $a({\mathbb{Z}}^d)$ of lattice animals as $d\to \infty$ , using a probabilistic method involving percolation theory. Along the way we also obtain new results on percolation.

1.1. Lattice animals

A lattice animal is a connected subgraph $S$ of the hypercubic lattice ${\mathbb{Z}}^d$ or more generally of a vertex-transitive graph $G$ . The counts of lattice animals with prescribed parameters have been extensively studied by scholars in statistical mechanics as well as combinatorics and computer science [4, 6, 11, 15, 19, 22, 36–38], both in ${\mathbb{Z}}^d$ and other lattices [5, 7, 39]. A lot of the motivation comes from the study of random configurations in ${\mathbb{Z}}^d$ , the central theme in many models of statistical mechanics. Our focus is Bernoulli (bond or site) percolation. Given a value of the percolation parameter $p\in [0,1]$ , we can express the probability $\theta (p)$ that the cluster $C_o$ of the origin $o$ is infinite as

(1) \begin{equation} 1-\theta (p) = \sum \nolimits_{A \text{ is a lattice animal containing } o}{\mathbb{P}}_p(C_o=A). \end{equation}

The probability ${\mathbb{P}}_p(C_o=A)$ is easily expressed as $p^{||A||} (1-p)^{|\partial A|}$ by the definition of bond percolation, where $||A||$ is the number of edges in $A$ , and the boundary $\partial A$ comprises the edges outside $A$ that are incident with $A$ . Thus, if we could enumerate the set of lattice animals $A_{n,m}$ with size $n$ and boundary size $m$ accurately enough, we could answer any question of percolation theory such as the continuity of $\theta (p)$ or the exact value of the critical threshold $p_c$ . In practice, however, $A_{n,m}$ is too difficult to enumerate, and one studies asymptotics as $n,m\to \infty$ . Such asymptotics, specifically the exponential growth rates, are still informative enough about the behaviour of percolation, and the present paper provides results in this vein.

1.2. Interfaces

Certain subfamilies of lattice animals, called interfaces, have also been extensively studied either as a tool in the study of statistical mechanics or for their own sake [10, 12]. The term interface is commonly used to denote the common boundary of two components of a crystal or liquid that are in a different phase. The precise meaning of the term varies according to the model in question and the perspective of its study. When studying percolation on a planar lattice $L$ for example, the interface of the cluster $C_o$ of the origin can be thought of as the minimal cut separating $C_o$ from infinity, which forms a cycle in the dual $L^*$ . Peierls’ argument [18] is a famous application of the notion that uses an upper bound on the number of such cycles to deduce an upper bound on $p_c(L)$ .

In [17], we introduced a variant of the notion of interface – see Definitions 3.3 and 3.6 – and used it to prove the analyticity of the percolation density $\theta (p)$ for supercritical Bernoulli percolation on ${\mathbb{Z}}^d$ . Our proof relied on the fact that our interfaces satisfy a generalisation of (1). Therefore, as argued above for lattice animals, counting interfaces accurately enough would yield important conclusions in percolation theory. This observation is the main motivation of this paper, which studies the exponential growth rate $b(G)$ of interfaces of a ‘lattice’ $G$ . Our first result is the following inequality relating $b(G)$ to ${p}_c(G)$ :

(2) \begin{equation} {b(G) \geq f(r({p}_c(G)))}, \end{equation}

where $f(r)\,:\!= \frac{(1+r)^{1+r}}{r^r}$ and $r(p)\,:\!=\frac{1-p}{p}$ are universal functions. The class $\mathcal S$ of lattices $G$ we work with includes the standard cubic lattice in ${\mathbb{Z}}^d, d\geq 2$ , as well as all doubly periodic planar lattices, which include any regular tessellation of the Euclidean plane; see Section 3 for the definition of $\mathcal{S}$ .

The fact that interfaces are a subspecies of lattice animals leads to the inequality $a(G)\geq b(G)$ . Inequality (2) allows us to translate any upper bound on the percolation threshold of a lattice $G$ into a lower bound on the exponential growth rate of lattice animals $a(G)$ and vice versa. We exploit this in both directions. We improve on the best known asymptotic lower and upper bounds on $a({\mathbb{Z}}^d)$ as $d\to \infty$ , answering a question of Barequet, Barequet and Rote [4]. We use percolation as a tool to obtain the latter, and conversely, we use the former to obtain lower bounds on $p_c({\mathbb{Z}}^d)$ .

1.3. Lattice animals vs. interfaces

Inequality (2) remains true if we replace $b(G)$ by the exponential growth rate $a(G)$ of lattice animals, and all ingredients for its proof are available in [19]. In this paper, we provide a unified, and simpler, approach to proving such inequalities. Our definition of interface is parametrised by a choice of a basis $\mathcal{P}$ of the cycle space ${\mathcal{C}}(G)$ of the lattice $G$ . We elaborate on this notion in Sections 3 and 4. By varying the choice of $\mathcal{P}$ , we obtain a spectrum of notions of $\mathcal{P}$ interface, which are always relevant to percolation: we showed in [17, Theorem 10.4] (restated as Theorem 3.7 below) that every finite connected subgraph of $G$ , for example a percolation cluster, contains a unique $\mathcal{P}$ interface. One extreme of this spectrum is where $\mathcal{P}$ is just the set of all cycles of $G$ , in which case the $\mathcal{P}$ interfaces coincide with the lattice animals. The other extreme is where $\mathcal{P}$ is a minimal basis, in which case the $\mathcal{P}$ interface of a percolation cluster is a thin layer incident with its boundary to infinity. For example, when $G$ is the square lattice, and $\mathcal{P}$ comprises its squares of length $4$ , then the (unique) $\mathcal{P}$ interface contained in a finite connected subgraph $C$ consists of the vertices and edges at the boundary of the unbounded face $F$ of $C$ in the plane. Here, we think of $C$ as a plane graph inheriting its embedding into ${\mathbb{R}}^2$ from $G$ , and the unbounded face of $C$ is its unique face of infinite diameter. Some examples of such interfaces are depicted in Figure 2. The main message of this paper is that this second extreme of $\mathcal{P}$ interfaces provides finer information about percolation. In particular, we will prove (Theorem 10.1) that for every basis $\mathcal{P}$ comprising cycles of bounded length the following holds:

Theorem 1.1. $b(G)\lt a(G)$ holds for every $G\in \mathcal{S}$ .

We remark that using this theorem and inequality (2), we obtain the strict inequality

\begin{equation*}{a(G) \gt f(r({p}_c(G)))}.\end{equation*}

1.4. Growth rates parametrised by ‘volume-to-surface ratio’

Before stating our other results, we need to introduce more terminology. Recall that when considering counts $A_{n,m}$ of lattice animals, it was important to parametrise them both by their size $n$ and their boundary size $m$ . Alternatively, instead of $m$ we could use the ‘volume-to-surface ratio’ $n/m$ . Similarly, to establish (2), we consider the exponential growth rate $b_r=b_r(G)$ of the number of interfaces of $G$ with size $n$ and volume-to-surface ratio approximating $r$ , as a function of $r\in{\mathbb{R}}_+$ . By ‘volume’ here we mean the number of edges contained in an interface $P$ , and by ‘surface’ we mean the cardinality of a set $\partial P$ of edges that are incident with $P$ and are ‘accessible’ from infinity. (See Definition 3.6 for details.) In the example of Figure 2, the edges in $\partial P$ are depicted by dashed lines.

We consider this function $b_r(G)$ to be of independent interest; in fact, most of this paper revolves around it. In particular, we prove that $b_r(G)$ is always continuous (Theorem 6.4) and log-concave (Theorem 6.3).

One of the best known results of percolation theory is the exponential decay, as $n\to \infty$ , of the cluster size distribution ${\mathbb{P}}_p(|C_o|= n)$ for $p$ in the subcritical interval $[0,p_c)$ [1]. In the supercritical case $p\in (p_c,1)$ , this exponential decay holds for some, but not all, lattices and values of $p$ [2, 24].

Letting $S_o \subseteq C_o$ denote the interface of $C_o$ , we can analogously ask for which $p\in (0,1)$ we have exponential decay of the probability ${\mathbb{P}}_p(|S_o|= n)$ . We prove that this is uniquely determined by the value $b_{r(p)}$ , where $r(p)\,:\!=\frac{1-p}{p}$ is a bijection between the parameter spaces of edge density $p$ and volume-to-surface ratio $r$ (we consider bond percolation in this section, but we will also discuss site percolation later on). More concretely, we observe that, firstly, $b_{r(p)}(G) \leq f(r(p))$ holds for every lattice $G$ and every $p\in (0,1)$ , where $f(r)$ is the aforementioned universal function (Proposition 4.4), and secondly, ${\mathbb{P}}_p(|S_o|= n)$ decays exponentially in $n$ for exactly those values of $p$ for which this inequality is strict:

Theorem 1.2. Let $G\in \mathcal{S}$ . Then for every $p\in (0,1)$ , the interface size distribution ${\mathbb{P}}_p( |S_o|=n )$ fails to decay exponentially in $n$ if and only if $$b_{r(p)}(G)= f(r(p)).$$

Incidentally, we prove in the Appendix that the rate of the exponential decay of ${\mathbb{P}}_p(|C_o|= n)$ , defined as $c(p)\,:\!= \lim _n \left ({\mathbb{P}}_p(|C_o|= n)\right )^{1/n}$ (see [3, 18] for a proof that the limit exists for every $p\in (0,1)$ ), is a continuous function of $p$ (Theorem 12.1). Our proof boils down to elementary calculations not involving our notion of interface. Another contribution of this paper is the subexponential decay at $1-p_c$ for triangulated lattices in ${\mathbb{R}}^d$ (Corollary 5.7).

We expect our results to hold for more general vertex-transitive 1-ended graphs, but decided to restrict our attention to $\mathcal{S}$ to avoid technicalities that would add little to the understanding of the matter.

It is interesting that Theorem 1.2 holds for every choice of basis $\mathcal{P}$ with respect to which our interfaces are defined. In particular, since lattice animals are a special case of $\mathcal{P}$ interfaces as mentioned above, we can replace the interface size distribution ${\mathbb{P}}_p( |S_o|=n )$ by the cluster size distribution ${\mathbb{P}}_p( |C_o|=n )$ and $b_{r(p)}(G)$ by its analogue $a_{r(p)}(G)$ counting lattice animals. This form of Theorem 1.2 was proved by Hammond [19] building on a result of Delyon [11].

Our proof of Theorem 1.2 is based on a large deviation principle for interfaces (Lemma 4.7) that may be of independent interest. Roughly speaking, the latter result says that for any $p\in (0,1)$ , most occurring interfaces have a volume-to-surface ratio close to the value $r(p)$ .

We mentioned above that the most refined extreme of such results is obtained when $\mathcal{P}$ is a minimal basis. This is even more so for ‘triangulated’ lattices, that is lattices having a basis $\mathcal{P}$ consisting of triangles. For such a lattice, we show that the following holds.

Theorem 1.3. Let $G\in \mathcal{S}$ , and suppose that the cycle space of $G$ is generated by its triangles. Then, $b_r= (b_{1/r})^r$ for every $r\gt 0$ .

In other words, the values of $b_r$ for $r\lt 1$ determine those for $r\gt 1$ (Theorems 5.1 and 5.2). This is the technically most involved result of this paper. It shows that considering interfaces rather than lattice animals yields a differently behaved function $b_r$ , namely one with no intersection with $f(r)$ not only for $r\gt r(p_c)$ but also for $r\lt 1/r(p_c)$ . Most of our knowledge about $b_r$ is summarised in Figure 1.

Figure 1. An approximate, conjectural, visualisation of $b_r(G)$ when $G$ is a lattice in ${\mathbb{R}}^d, d\geq 3$ . The graph of $b_r(G)$ (depicted in bold ink) lies below the graph of $f(r)\,:\!= \frac{(1+r)^{1+r}}{r^r}$ (depicted in blue, if colour is shown). The fact that $f(r)$ plots almost like a straight line can be seen by rewriting it as $(1+r)(1+1/r)^r$ . The fact that $b_r= f(r)$ for $r$ in the interval $(r(1-p_c), r(p_c)]$ , where $r(p)\,:\!= \frac{1-p}{p}$ , follows by combining a theorem of Kesten & Zhang [29], saying that exponential decay of ${\mathbb{P}}_p(|S_o|= n)$ fails in that interval, with our Theorem 1.2. That $b_r\lt f(r)$ for $r\gt r(p_c)$ follows from the well-known exponential decay of ${\mathbb{P}}_p(|C_o|= n)$ for $p\lt p_c$ [1]. We also know that $b_r$ is continuous and log-concave. The continuity of $b_r$ , combined with Theorem 1.2 again, implies failure of the exponential decay at $p=1-p_c$ (Corollary 5.7), which was not obtained in [29]. If the cycle space of $G$ is generated by its triangles, then Theorem 1.3 determines the subcritical branch $r\gt r(p_c)$ given the branch $r\lt r(1-p_c)$ and vice versa. For the planar triangular lattice, the picture degenerates as $p_c=1-p_c=1/2$ , and so $b_r= f(r)$ for $r=r(1/2)=1$ only. Note that $b_r(G)$ is an invariant of $G$ defined without reference to any random experiment. The connection to percolation is established by Theorem 1.2 via the above transformation $r(p)$ . Since $r(p)$ is monotone decreasing in $p$ , the right-hand side of Figure 1 corresponds to the subcritical percolation regime, and the left-hand side to the supercritical. Using the transformation $r\to \frac 1{r}$ (from volume-to-surface into surface-to-volume ratio), we could reverse the picture to have the ‘subcritical’ interval on the left. For ‘triangulated’ lattices, the picture would look exactly the same due to Theorem 1.3, only the positions of $r(p_c)$ and $r(1-p_c)$ would be interchanged.

Amusingly, our universal function $f(r)$ also satisfies the equation of Theorem 1.3, that is $f(r)= f(1/r)^r$ .

1.5. Bounds on lattice animals

Obtaining reasonable bounds on the count $a_n({\mathbb{Z}}^d)$ of $d$ -dimensional lattice animals of size $n$ containing the origin is very difficult to come by even in 2 dimensions, and so the mainstream focuses on their exponential growth rates $a({\mathbb{Z}}^d)\,:\!=\lim _{n\to \infty }{a_n({\mathbb{Z}}^d)}^{1/n}$ . These have important interactions with statistical mechanics models such as percolation theory, the present paper being an instance of this interaction. Some precise asymptotic expansions for $a({\mathbb{Z}}^d)$ and its site counterpart $\dot{a}({\mathbb{Z}}^d)$ were reported in the physics literature [15, 22, 38] but without any rigorous bounds on the error terms. Miranda and Slade [36, 37] determined the first three terms of the $1/d$ expansion of $a({\mathbb{Z}}^d)$ rigorously.

Much less is known about its site variant $\dot{a}({\mathbb{Z}}^d)$ . Barequet, Barequet, and Rote in [4] proved that $\dot{a}({\mathbb{Z}}^d)=2de-o(d)$ . Peard and Gaunt had previously made involved, but nonrigorous, calculations that yield $\dot{a}({\mathbb{Z}}^d)=2de-3e+O(1/d)$ [38, (2.22)] and [4] expressed the belief that this is correct. Our first result is that this prediction is indeed right as a lower bound (Theorem 7.5). We deduce this from a recent bound of Heydenreich and Matzke [25] on the site percolation threshold ${\dot{p}_c}({\mathbb{Z}}^d)$ , obtained using an involved technique called lace expansion. (The dot in ${\dot{p}_c}({\mathbb{Z}}^d),\dot{a}({\mathbb{Z}}^d)$ etc. means that we are considering site percolation, or lattice site animals; most of our results have a bond and a site version.) To do so, we exploit the aforementioned formula (2).

The aforementioned upper bound of [4] was improved to $\dot{a}({\mathbb{Z}}^d)\leq 2de-2e+1/(2d-2)$ in simultaneous work by Barequet and Shalah [6]. We improve this further asymptotically to $\dot{a}({\mathbb{Z}}^d)\leq 2de-5e/2+O(1/\log\! (d))$ (Theorem 8.1). For this, we use direct combinatorial arguments that do not involve percolation. We can then plug this bound into (the site version of) (2) to obtain the lower bound ${\dot{p}_c}({\mathbb{Z}}^d)\geq \frac{1}{2d}+\frac{2}{(2d)^2}-O(1/d^2\log\! (d))$ (Theorem 8.4). This bound was improved by Heydenreich and Matzke [25] shortly after the first draft of our work appeared, see (17).

In this paper, we used percolation as a tool to bound $\dot{a}({\mathbb{Z}}^d)$ from above. Another method was introduced by Eden [13] using more direct counting arguments. This method was enhanced by Klarner and Rivest [31] in the case of ${\mathbb{Z}}^2$ , who obtained that $\dot{a}({\mathbb{Z}}^2)\leq 4.6496$ , and more recently by Barequet and Shalah [6], who obtained the asymptotic inequality $\dot{a}({\mathbb{Z}}^d)\leq 2de-2e+1/(2d-2)$ . In dimension $3$ , the same paper proves $\dot{a}({\mathbb{Z}}^3)\lt 9.3835$ . Plugging this into (2), we deduce $\dot{p}_c({\mathbb{Z}}^3)\gt 0.2522$ , which is the best rigorous lower bound known.

1.6. Improvements for non-amenable graphs

A well-known theorem of Benjamini & Schramm [8] states that $p_c(G)\leq \frac{1}{h(G)+1}$ , where $h(G)$ denotes the Cheeger constant. We show that this inequality is in fact strict, that is

\begin{equation*} p_c(G)\lt \frac{1}{h(G)+1},\end{equation*}

when $G$ is $1$ -ended, has bounded degrees, and its cycle space admits a basis consisting of cycles of bounded length (Theorem 10.2). Moreover, in Section 9 we define a variant $I(G)$ of the Cheeger constant by considering interfaces rather than arbitrary finite subgraphs of $G$ . We obtain the strengthening $p_c(G)\leq \frac{1}{I(G)+1}$ of the aforementioned theorem (Theorem 9.2), which again has a site and a bond version. We remark that, unlike $h(G)$ , our $I(G)$ can be positive even for amenable graphs. When $G$ is the planar square lattice for example, it is not hard to see that $I(G)=1/2$ in the bond case, which yields the Peierls bound $p_c\leq 2/3$ . Moreover, one can have $I(G)\gt h(G)$ even in the non-amenable case: this turns out to be the case for regular triangulations and quadrangulations of the hyperbolic plane as proved in a companion paper [23].

1.7. Structure

This paper is structured as follows. Section 2 contains some standard definitions and results that will be used in several places later on. Section 3 recalls the notion of an interface and some of its properties obtained in [17]. Section 4 introduces $b_r$ and presents the proof of the inequality $b_r\leq f(r)$ and Theorem 1.2. Sections 5 and 6 contain a proof of Theorem 1.3 and the fact that $b_r$ is well-behaved, namely continuous and log-concave. In Sections 7 and 8, we obtain the bounds on lattice animals and the lower bound on $\dot{p}_c({\mathbb{Z}}^3)$ . The last two sections are devoted to the new bounds on $p_c$ for non-amenable graphs and to the proof of Theorem 1.1. The Appendix contains a proof that the rate of the exponential decay of the cluster size distribution of Bernoulli percolation is a continuous function of $p\in (0,1)$ . An analogous result is proved for interfaces as well.

2. Definitions and preliminaries

2.1. Percolation

We recall some standard definitions of percolation theory. For more details, the reader can consult, for example, [9, 18, 33].

Let $G = (V,E)$ be a countably infinite graph, and let $\Omega \,:\!= \{0,1\}^E$ be the set of percolation configurations on $G$ . We say that an edge $e$ is vacant (respectively, occupied) in a percolation configuration $\omega \in \Omega$ , if $\omega (e)=0$ (resp. $\omega (e)=1$ ).

By Bernoulli bond percolation on $G$ with parameter $p\in [0,1]$ , we mean the random subgraph of $G$ obtained by keeping each edge with probability $p$ and deleting it with probability $1-p$ , with these decisions being independent of each other.

The percolation threshold $p_c(G)$ is defined by

\begin{equation*}p_c(G)\,:\!= \sup \left\{p \mid {\mathbb {P}}_p(|C_o|=\infty )=0\right\},\end{equation*}

where the cluster $C_o$ of $o\in V$ is the component of $o$ in the subgraph of $G$ spanned by the occupied edges. It is easy to see that $p_c(G)$ does not depend on the choice of $o$ .

To define site percolation, we repeat the same definitions, except that we now let $\Omega \,:\!= \{0,1\}^V$ , and let $C_o$ be the component of $o$ in the subgraph of $G$ induced by the occupied vertices. The percolation threshold for site percolation is denoted $\dot{p}_c$ .

In this paper, the graphs $G$ we consider are all countably infinite, connected, and every vertex has finite degree. Some of our results will need assumptions on $G$ like (quasi-)vertex transitivity or planarity, but these will be explicitly stated as needed.

2.2. Graph-theoretic definitions

Let $G = (V,E)$ be a graph. An induced subgraph $H$ of $G$ is a subgraph that contains all edges $xy$ of $G$ with $x,y\in V(H)$ . Note that $H$ is uniquely determined by its vertex set. The subgraph of $G$ spanned by a vertex set $S\subseteq V(G)$ is the induced subgraph of $G$ with vertex set $S$ . The vertex set of a graph $G$ will be denoted by $V(G)$ , and its edge set by $E(G)$ . The degree of a vertex $v\in V(G)$ is the number of edges of $G$ containing $v$ .

The edge space of a graph $G$ is the direct sum ${\mathcal E}(G)\,:\!= \bigoplus _{e\in E(G)}{\mathbb{Z}}_2$ , where ${\mathbb{Z}}_2=\{0,1\}$ is the field of two elements, which we consider as a vector space over ${\mathbb{Z}}_2$ . The cycle space ${\mathcal{C}}(G)$ of $G$ is the subspace of ${\mathcal E}(G)$ spanned by the circuits of cycles, where a circuit is an element $C\in{\mathcal E}(G)$ whose non-zero coordinates $\{e\in E(G) \mid C_e=1\}$ coincide with the edge set of a cycle of $G$ . By a cycle, we mean a connected subgraph $C$ every vertex of which lies in exactly two edges of $C$ .

Given a subgraph $S$ of ${\mathbb{Z}}^d$ , the edge boundary $\partial _E S$ of $S$ is the set of edges of ${\mathbb{Z}}^d$ that have at least one end vertex in $S$ but are not contained in $S$ . The vertex boundary $\partial _V S$ of $S$ is the set of vertices of ${\mathbb{Z}}^d$ that have a neighbour in $S$ but are not contained in $S$ .

A planar graph $G$ is a graph that can be embedded in the plane ${\mathbb{R}}^2$ , that is it can be drawn in such a way that no edges cross each other. Such an embedding is called a planar embedding of the graph. A plane graph is a (planar) graph endowed with a fixed planar embedding. Alternatively, we can think of a plane graph as a subspace of ${\mathbb{R}}^2$ homeomorphic to an 1-complex.

A plane graph $G$ divides the plane into regions called faces, that is each face is a connected component of ${\mathbb{R}}^2\setminus G$ . Using the faces of a plane graph $G$ , we define its dual graph $G^*$ as follows. The vertices of $G^*$ are the faces of $G$ , and we connect two vertices of $G^*$ with an edge whenever the corresponding faces of $G$ share an edge. Thus, there is a bijection $e\mapsto e^*$ from $E(G)$ to $E(G^*)$ .

Given a subgraph $H$ of a graph $G$ and a positive integer $k$ , we define the k-neighbourhood of $H$ to be the set of vertices at distance at most $k$ from $H$ .

2.3. Partitions

A partition of a positive integer $n$ is a multiset $\{m_1,m_2,\ldots,m_k\}$ of positive integers such that $m_1+m_2+\ldots +m_k=n$ . Let $p(n)$ denote the number of partitions of $n$ . An asymptotic expression for $p(n)$ was given by Hardy & Ramanujan in their famous paper [21]. An elementary proof of this formula up to a multiplicative constant was given by Erdős [14]. As customary, we use $A\sim B$ to denote the relation $A/B\rightarrow 1$ as $n\rightarrow \infty$ .

Theorem 2.1 (Hardy-Ramanujan formula). The number $p(n)$ of partitions of $n$ satisfies

\begin{equation*}p(n)\sim \dfrac {1}{4n\sqrt {3}}\exp \left (\pi \sqrt {\dfrac {2n}{3}}\right ).\end{equation*}

(We do not need the full strength of Theorem 2.1 in this paper; any subexponential upper bound on $p(n)$ would suffice, and such bounds are much easier to obtain. See for example [17, Lemma 3.4].)

2.4. Doubly periodic planar lattices

In this subsection, we will consider graphs that embed in $\mathbb{R}^2$ , in a ‘nice’ way.

Definition 2.2. A doubly periodic planar lattice is a locally finite, connected, plane graph $G$ without accumulation points of vertices, such that for some linearly independent vectors $v_1,v_2\in{\mathbb{R}}^2$ , translation by each $v_i$ preserves $G$ .

Notice that any action as in Definition 2.2 has finitely many orbits of vertices.

Definition 2.3. Given a finite subgraph $H$ of an infinite graph $G$ , the minimal edge cut $\partial ^E H$ of $H$ is defined to be the minimal set of edges lying in $E(G)\setminus E(H)$ with at least one end vertex in $H$ , the removal of which disconnects $H$ from infinity. The minimal vertex cut $\partial ^V H$ of $H$ is the minimal set of vertices in $V(G)\setminus V(H)$ that are incident to $H$ , the removal of which disconnects $H$ from infinity.

To see that the minimal sets in the above definition are unique, note that $\partial ^E H$ and $\partial ^V H$ can be defined equivalently as the sets of edges/vertices that are incident to $H$ and connected to infinity in the complement of $\partial _E H$ and $\partial _V H$ , respectively.

It is not hard to see that doubly periodic planar lattices are quasi-isometric to ${\mathbb{R}}^2$ , inheriting some of its geometric properties. More precisely, any doubly periodic planar lattice $G$

1. P1 has quadratic growth, that is there are constants $c_1=c_1(G),c_2=c_2(G)\gt 0$ such that

   \begin{equation*}c_1 n^2\leq |B(u,n)|\leq c_2 n^2\end{equation*}
   for every $u\in V(G)$ and every positive integer $n$ , where $B(u,n)$ denotes the ball of radius $n$ around $u$ in either graph-theoretic distance or Euclidean distance,

2. P2 satisfies a $2$ -dimensional isoperimetric inequality, that is there is a constant $c=c(G)\gt 0$ such that for any finite subgraph $H\subset G$ ,

   \begin{equation*}|\partial ^V H|\geq c \sqrt {|H|}.\end{equation*}

It will be useful to define a more general type of isoperimetric inequality.

1. P3 Given a positive number $d$ (not necessarily an integer), we say that a graph $G$ satisfies a $d$ -dimensional isoperimetric inequality if there is a constant $c\gt 0$ such that for any finite subgraph $H\subset G$ ,

   \begin{equation*}|\partial ^V H|\geq c |H|^{\frac {d-1}{d}}.\end{equation*}

Any doubly periodic planar lattice $G$ is easily seen to satisfy the following properties as well:

1. P4 For some $o\in V(G)$ , there is a $2$ -way infinite path $X=(\ldots,x_{-1},x_0=o,x_1,\ldots )$ containing $o$ and a constant $\ell \gt 0$ , such that $d_X(x_i,x_j)\leq \ell d_G(x_i,x_j)$ for every $i,j\in \mathbb{Z}$ , where $d_X$ and $d_G$ denote distance in $X$ and $G$ , respectively. Moreover, it is not too hard to see that we can choose $X$ to be periodic, that is to satisfy $X+ t v_1= X$ for some $t\in{\mathbb N}$ . Any such path is called a quasi-geodesic.

2. P5 The cycle space of $G$ is generated by cycles of bounded length.

   Indeed, a natural choice for a basis of the cycle space of $G$ is the set of cycles which bound a face of $G$ , which all have length bounded by a uniform constant by periodicity.

3. P6 $G$ is $1$ -ended, that is for every finite subgraph $H$ of $G$ , the graph $G\setminus H$ has a unique infinite component.

3. Interfaces

In this section, we recall the notions of (bond-)interfaces and site interfaces introduced in [17]. In most cases, we will work with the following families of graphs:

1. (a) doubly periodic planar lattices,

2. (b) the standard cubic lattice ${\mathbb{Z}}^d$ , $d\geq 2$ ,

3. (c) $\mathbb{T}^d$ , the graph obtained by adding to ${\mathbb{Z}}^d$ , $d\geq 2$ the ‘monotone’ diagonal edges, that is the edges of the form $xy$ where $y_i-x_i=1$ for exactly two coordinates $i\leq d$ , and $y_i=x_i$ for all other coordinates ( $\mathbb{T}^2$ is isomorphic to the triangular lattice).

Definition 3.1. We define $\mathcal{S}$ to be the set of all $2$ -connected doubly periodic planar lattices, and the lattices ${\mathbb{Z}}^d$ and $\mathbb{T}^d$ for $d\geq 2$ .

Remark 3.2. The $2$ -connectedness restriction is helpful because it implies that every vertex is contained in a cycle of the graph. This is only a minor restriction, because any cut vertices separate finite components by 1-endedness, and those components can be removed to obtain a $2$ -connected doubly periodic planar lattice on which percolation behaves in the same way as in the initial graph, for example it has the same $p_c$ , for a fixed $p\in (0,1)$ either ${\mathbb{P}}_p(|S_o|=n)$ decays exponentially for both graphs or for none of them, etc.

Our motivation for considering $\mathbb{T}^d$ is that ${\mathbb{Z}}^d$ fails to satisfy Theorem 1.3, our deepest result, while $\mathbb{T}^d$ is a ‘minimal’ supergraph of ${\mathbb{Z}}^d$ that satisfies it. The reason for this is that $\mathbb{T}^d$ satisfies the assumption that the cycle space is generated by triangles, while ${\mathbb{Z}}^d$ does not. The same applies to variants of $\mathbb{T}^d$ obtained by adding more ‘diagonal’ edges, but we will refrain from discussing those variants.

For each $G\in \mathcal{S}$ , we will fix a basis $\mathcal{P}=\mathcal{P}(G)$ of the cycle space ${\mathcal{C}}(G)$ (defined in Section 2.2). If $G$ is a doubly periodic planar lattice, $\mathcal{P}$ consists of the cycles bounding the faces of $G$ . For $G={\mathbb{Z}}^d$ , we can use the squares of length $4$ as our basis $\mathcal{P}$ , and for $G=\mathbb{T}^d$ , we can use the triangles obtained from the squares of length $4$ once we add the ‘monotone’ diagonal edges. Our definition of the interface of $G$ depends on the choice of $\mathcal{P}(G)$ , and so in [17], we used the notation ‘ $\mathcal{P}$ interface’ to emphasise the dependence. Since in this paper we are fixing $\mathcal{P}(G)$ for each $G\in \mathcal{S}$ , we will simplify our notation and just talk about interfaces.

Let us start by defining interfaces for doubly periodic planar lattices.

Definition 3.3. Let $G$ be a doubly periodic planar lattice and $o$ a vertex of $G$ . A subgraph $P$ of $G$ is called a (bond-)interface (of $o$ ) if there is a finite connected subgraph $H$ of $G$ containing $o$ such that $P$ consists of the vertices and edges incident with the unbounded face of $H$ . The boundary $\partial P$ of $P$ is the set of edges of $G$ that are incident with $P$ and lie in the unbounded face of $H$ . We say that an interface occurs in a bond percolation configuration $\omega$ if all edges in $P$ are occupied and all edges in $\partial P$ are vacant.

As remarked in [17, Proposition 10.7] interfaces are connected graphs and satisfy the following property.

Lemma 3.4. For any doubly periodic planar lattice $G$ , if two interfaces of $G$ occur in the same percolation configuration $\omega$ and share a vertex then they coincide.

With some thought, this notion can be generalised to higher dimensions in such a way that a unique interface is associated with any cluster. The reader may already have their own favourite definition of interface for $G={\mathbb{Z}}^d$ or $G=\mathbb{T}^d$ , and as long as that definition satisfies Theorem 3.7 below, it will coincide with ours. For the remaining readers, we offer the following abstract definition. For (site percolation on) $G=\mathbb{T}^d$ , we offer a simpler alternative definition implicit in Proposition 3.9.

In [17], we were able to define interfaces in much greater generality than that of graphs in $\mathcal{S}$ , namely in every $1$ -ended, $2$ -connected graph $G$ . These interfaces have the important property that in any percolation configuration, occurring interfaces are in 1-to-1 correspondence with percolation clusters (Theorem 3.7 below). A priori it is not clear that such a general and well-behaved definition of interface is possible. To come up with it, we have tried to capture the important features of interfaces in Definition 3.3 without reference to the embedding of $G$ . For this, we noticed that fixing an embedding of a graph into ${\mathbb{R}}^2$ is tantamount to fixing the cycles that bound faces. Thus to generalise Definition 3.3 to an arbitrary graph, we need a notion of ‘face boundaries’. The role of this notion is played in our definition by a choice of a generating set of a cycle space ${\mathcal{C}}(G)$ of $G$ . (For an 1-ended 2-connected plane graph, the face boundaries form a basis of the cycle space.)

We proceed with our formal definition of interfaces. From now on, we will be assuming that

(3) \begin{equation} G\ \text{is an } 1-\text{ ended, } 2-\text{ connected graph.} \end{equation}

Every edge $e=vw\in E(G)$ has two directions $\vec{vw},\overleftarrow{wv}$ , which are the two directed sets comprising $v,w$ . We let $\overleftrightarrow{E(G)}$ denote the set of all directions of edges in $E(G)$ . The head $head(\vec{vw})$ of $\vec{vw}$ is $w$ . Given $F\subset E(G)$ and a subgraph $D$ of $G$ , let ${\vec{F^{D}}}\,:\!= \{\vec{vz} \mid vz\in F, z\in V(D) \}$ be the set of directions of the elements of $F$ towards $D$ .

Let $\mathcal{P}$ denote a basis of ${\mathcal{C}}(G)$ (which in the particular case of $\mathcal{S}$ we fixed at the beginning of this section). A $\mathcal{P}$ -path connecting two directed edges $\vec{vw}, \overleftarrow{yx} \in \overleftrightarrow{E(G)}$ is a path $P$ of $G$ such that the extension $vw P yx$ is a subpath of an element of $\mathcal{P}$ . Here, the notation $vw P yx$ denotes the path with edge set $E(P) \cup \{vw, yx\}$ , with the understanding that the end vertices of $P$ are $w,y$ . Note that $P$ is not endowed with any notion of direction, but the directions of the edges $\vec{vw}, \overleftarrow{yx}$ it connects do matter. We allow $P$ to consist of a single vertex $w=y$ .

We will say that $P$ connects an undirected edge $e\in E(G)$ to $\vec{f}\in \overleftrightarrow{E(G)}$ (respectively, to a set $J\subset \overleftrightarrow{E(G)}$ ), if $P$ is a $\mathcal{P}$ -path connecting one of the two directions of $e$ to $\vec{f}$ (resp. to some element of $J$ ).

Definition 3.5. We say that a set ${J}\subset \overleftrightarrow{E(G)}$ is $F$ -connected for some $F\subset E(G)$ , if for every proper bipartition $ ({J_1},{J_2})$ of $J$ , there is a $\mathcal{P}$ -path in $G$ that avoids $F$ and connects an element of $J_1$ to an element of $J_2$ .

We are now ready to give the formal definition of the central notion of the paper.

Definition 3.6. A (bond-)interface of $G$ is a pair $(P,\partial P)$ of sets of edges of $G$ with the following properties

1. (i) $\partial P$ separates $o$ from infinity;

2. (ii) Exactly one finite component of $G\setminus \partial P$ , denoted by $D$ , contains a vertex of each edge in $\partial P$ ;

3. (iii) $\vec{\partial P^{D}}$ is $\partial P$ -connected; and

4. (iv) $P = \big\{e \in E(D) \mid \text{ there is\ a $\mathcal{P}$-path in $G\setminus \partial P$ connecting $e$ to ${\vec{\partial P^{D}}}$ }\big\}$ .

Recall that we are thinking of $\mathcal{P}$ as a generalisation of the face boundaries of a planar graph. Notice that for $P$ as in Definition 3.3, the faces outside $P$ connect the edges in $\partial P$ . Condition (iii) is the analogue of this observation.

We say that an interface $(P,\partial P)$ occurs in a bond percolation configuration $\omega$ if the edges of $P$ are occupied, and the edges of $\partial P$ are vacant. Moreover, we say that $(P,\partial P)$ meets a cluster $C$ of $\omega$ , if either $P\cap E(C)\neq \emptyset$ , or $P = E(C) =\emptyset$ and $\partial P=\partial C$ , where $\partial C$ is the set edges in $E(G)\setminus E(C)$ with at least one end vertex in $C$ (in which case $C$ consists of $o$ only).

Example 1: Let $G$ be a 2-connected doubly periodic planar lattice, and let $\mathcal{P}$ consist of the cycles bounding a face of $G$ . Then, Definitions 3.3 and 3.6 agree. It would be a good exercise for the reader to check this in specific cases: draw a portion of your favourite lattice, and a random finite connected subgraph $H$ . Guess what the interface $P$ of $H$ should be based on Definition 3.3. Then, check that the pair $(P,\partial P)$ as in Definition 3.3 satisfies the conditions of Definition 3.6.

Example 2: Let $G$ be any 1-ended 2-connected graph, and choose $\mathcal{P}$ to be the set of all cycles of $G$ . Then for every finite $P\subset E(G)$ spanning a connected subgraph of $G$ , the pair $(P,\partial P)$ is an interface, where $\partial P$ is the set of edges of $G$ incident with $P$ . To see this, use the fact that every pair of edges of $\partial P$ lies in a common cycle $C$ by 2-connectedness. Notice the rigidity: there is no $Q\neq \partial P\subset E(G)$ such that $(P,Q)$ is an interface.

Example 3: We can ‘interpolate’ between examples 1 and 2 by fixing $G$ and $H$ , and varying $\mathcal{P}$ . For example, let $H$ be the ball of radius $N\in{\mathbb N}$ around $o$ , and let $\mathcal{P} =\mathcal{P}_r$ consist of all cycles of $G$ of length at most $r$ . Then, there is a unique interface $(P,\partial P)$ such that $\partial P=\partial H$ , and $P$ becomes thicker as $r$ grows.

The following result shows that in any percolation configuration, occurring interfaces are in 1-to-1 correspondence with percolation clusters.

Theorem 3.7 ([17, Theorem 10.4]). Let $G$ be an 1-ended, 2-connected graph, and $\omega$ a (site) percolation configuration. For every finite (site) percolation cluster $C$ of $\omega$ such that $\partial _E C$ separates $o$ from infinity, there is a unique (site)interface $(P,\partial P)$ that meets $C$ and occurs. Moreover, we have $P\subset E(C)$ and $\partial P\subset \partial C$ .

Conversely, every occurring (site)interface meets a unique percolation cluster $C$ , and $\partial C$ separates $o$ from infinity (in particular, $C$ is finite).

The above result allows us to define the interface of a finite cluster $C$ of a percolation configuration $\omega$ as the unique occurring interface that meets $C$ . (There can be clusters $C$ that separate $o$ from infinity and do not contain $o$ ; for example, if $G$ is planar, $C$ could be a cycle around $o$ .)

(Bond-)interfaces are specifically designed to study bond percolation on $G$ . There is a natural analogue for site percolation. For an interface $(Q,\partial Q)$ of $G$ , we let $V(Q)$ denote the set of vertices incident with an edge in $Q$ , and we let $V(\partial Q)$ denote the set of vertices in $V\setminus V(Q)$ which are incident with an edge in $\partial Q$ . We say that a pair $(P,\partial P)$ of vertex sets is a site interface, if $P=V(Q)$ and $\partial P=V(\partial Q)$ for a bond-interface $(Q,\partial Q)$ with the property that no edge in $\partial Q$ has both its end vertices in $V(Q)$ . We emphasise that a site interface is a pair of vertex sets, while a bond interface is a pair of edge sets. This is a crucial difference for results such as Theorem 3.7.

We say that a site interface $(P,\partial P)$ occurs in a site percolation configuration $\omega$ if the vertices of $P$ are occupied, and the vertices of $\partial P$ are vacant. We define the site interface of a cluster $C$ of a site percolation configuration $\omega$ as the occurring site interface that has at least one common vertex with $C$ . The fact that there exists a unique such site interface follows from Theorem 3.7.

Remark 3.8. Let $G$ be a graph whose cycle space admits a basis consisting of cycles of length bounded by some constant $t\gt 0$ . Then for every interface $(P,\partial P)$ of $G$ , and any pair of edges in $\partial P$ , there is a path contained in the $t/2$ -neighbourhood of $\partial P$ connecting the pair (see [17, p. 47]).

We define a (site)multi-interface to be a finite collection of (site)interfaces $(P_1,\partial P_1),\ldots,(P_n,\partial P_n)$ such that the sets $P_i$ are pairwise disjoint. An example is shown in Figure 2.

Figure 2. An example of a multi-interface $M$ , comprising two nested interfaces $P_1,P_2$ . We depict $M$ with bold lines, and $\partial M\,:\!= \partial P_1 \cup \partial P_2$ with dashed lines (green, if colour is shown). The edges not participating in $M$ are depicted in plain lines (blue, if colour is shown).

In the case where

(4) \begin{equation} G\in \mathcal{S} \,\text{is a graph whose cycle space is generated by its triangles,} \end{equation}

site interfaces admit an equivalent definition that is more standard and easier to work with:

Proposition 3.9. Let $G\in \mathcal{S}$ be a graph satisfying (4), and let $D$ be a finite induced subgraph of $G$ containing $o$ . Let $\overline{D}$ be the union of $D$ with the finite connected components of $G\setminus D$ . Define $P$ to be the set of vertices of $\overline{D}$ which have a neighbour not in $\overline{D}$ , and let $\partial P$ be the set of vertices of $G\setminus \overline{D}$ that have a neighbour in $\overline{D}$ . Then, $(P,\partial P)$ is the site interface of $D$ . Moreover, any site interface can be obtained in this way.

Proof. Let us start from the last statement which is easier to prove. By definition, for every site interface $(P,\partial P)$ , $G\setminus \partial P$ has a unique finite component $D$ . Notice that $G\setminus D$ has no finite components, that is $\overline{D}=D$ . Now $\partial P$ is the set of vertices of $G\setminus \overline{D}$ that have a neighbour in $\overline{D}$ . Moreover, all vertices of $\overline{D}$ which have a neighbour not in $\overline{D}$ belong to $P$ . On the other hand, each vertex $u$ of $P$ has a neighbour in $\partial P$ because there is a $\mathcal{P}$ -path connecting $u$ to $\partial P$ and $G$ satisfies (4).

Let $L$ be the set of edges with one end vertex in $P$ and another in $\partial P$ , and let $Q$ be the set of edges $e$ in $E(D)$ such that there is a $\mathcal{P}$ -path in $G\setminus L$ connecting $e$ to $\vec{L^{D}}$ . If $e$ is an edge in $Q$ , then both its end vertices are incident with an edge in $L$ ; hence, both of them lie in $P$ , because $\mathcal{P}$ contains only triangles, and $D$ is an induced subgraph. It suffices to show that $(Q,L)$ is the interface of $D$ , as this will immediately imply that $(P,\partial P)$ is the corresponding site interface of $D$ .

It is easy to verify that $L$ satisfies the first two items of Definition 3.6 and that $Q$ satisfies the last item of the definition. It remains to prove that $\vec{L^{D}}$ is $L$ -connected. Assuming not, we find a proper bipartition $(L_1,L_2)$ of $L$ , such that no $\mathcal{P}$ -path connects $L_1$ with $L_2$ . Consider $e\in L_1$ and $f\in L_2$ . Then, there are two paths connecting $e$ with $f$ , where one of them lies in $D$ and the other one lies in the complement of $D$ . The union of the two paths with $e$ and $f$ is a cycle, which we denote $K$ .

Since $\mathcal{P}$ is a basis for the cycle space ${\mathcal{C}}(G)$ , $K$ can be expressed as a sum $\sum C_i$ of cycles $C_i\in \mathcal{P}$ . Let $L_{C_i}\,:\!= \overleftrightarrow{L \cap E(C)}$ be the directions of edges of $L$ appearing in $C_i$ . Note that no cycle $C_i$ contains a path in $G\setminus L$ connecting $L_1$ to $L_2$ , because no such path exists by the choice of $(L_1,L_2)$ . Consequently, $L_{C_i}$ has an even number of its elements in each of $L_1,L_2$ , because each component of $C_i\setminus L$ (which is a subpath of $C_i$ ) is incident with either 0 or 2 such elements pointing towards the component, and they lie both in $L_1$ or both in $L_2$ or both in none of the two.

This leads into a contradiction by a parity argument: notice that our cycle $K$ contains an odd number of directions of edges in each of $L_1,L_2$ , namely exactly one in each – $e$ and $f$ respectively – because $P$ avoids $L$ and $Q$ avoids $D$ , hence $\vec{L^{D}}$ , by definition. But then, our equality $K=\sum C_i$ is impossible by the above claim because sums in ${\mathcal{C}}(G)$ preserve the parity of the number of (directed) edges in any set. This contradiction proves our statement.

Most of the time, we will write $P$ instead of $(P,\partial P)$ to simplify the notation.

4. Growth rates

In this section, we give the formal definition of $b_r$ in its bond and site version, obtain some basic facts about it, and establish the connection to percolation.

Given a graph $G$ , we let $I_{n,r,\epsilon }=I_{n,r,\epsilon }(G)$ denote the set of interfaces $P$ with $|P|=n$ and $(r-\epsilon )n \leq |\partial P| \leq (r+\epsilon )n$ . Here, $|\!\cdot\! |$ counts the number of edges. Similarly, we let $MI_{n,r,\epsilon }=MI_{n,r,\epsilon } (G)$ denote the set of multi-interfaces $P$ with $|P|=n$ and $(r-\epsilon )n \leq |\partial P| \leq (r+\epsilon )n$ .

To avoid introducing a cumbersome notation, we will still write $I_{n,r,\epsilon }$ and $MI_{n,r,\epsilon }$ for the site interfaces and site multi-interfaces, respectively, of size $n$ and boundary size between $(r-\epsilon )n$ and $(r+\epsilon )n$ . Moreover, we will write $c_{n,r,\epsilon }^\circ$ and $c_{n,r,\epsilon }^\odot$ for the cardinality of $I_{n,r,\epsilon }$ and $MI_{n,r,\epsilon }$ , respectively.

The definitions, results, and proofs that follow apply to both (bond)interfaces and site interfaces unless otherwise stated.

Definition 4.1. Define the (upper) exponential growth rate $b_r^\circ (G)$ of the (bond or site) interfaces of $G$ with surface-to-volume ratio $r$ by

\begin{equation*}b_r^\circ =b_r^\circ (G)\,:\!= \lim _{\epsilon \to 0} \limsup _{n\to \infty } {c_{n,r,\epsilon }^\circ (G)}^{1/n}.\end{equation*}

Similarly, we define the (upper) exponential growth rate $b_r^\circ (G)$ of the (site)multi-interfaces of $G$ with surface-to-volume ratio $r$ by

\begin{equation*}b_r^\odot =b_r^\odot (G)\,:\!= \lim _{\epsilon \to 0} \limsup _{n\to \infty } {c_{n,r,\epsilon }^\odot (G)}^{1/n}.\end{equation*}

We remark that in Hammond’s definition of the exponential growth rate of lattice animals with surface-to-volume ratio $r$ , $\epsilon$ depends on $n$ . The above definition simplifies the proofs of some of the following results.

We are going to study $b_r^\circ$ and $b_r^\odot$ as functions of $r$ . As it turns out, these two functions coincide:

Lemma 4.2. Let $G\in \mathcal{S}$ . Then, $b_r^\circ (G) = b_r^\odot (G)$ .

We postpone the proof until the next section where the necessary definitions and tools are introduced.

From now on, except for the proof of Lemma 4.2, we will drop the superscripts and we will simply write $b_r$ and $c_{n,r,\epsilon }$ . In our proofs, we will work with interfaces and site interfaces instead of multi-interfaces and site multi-interfaces.

Similarly to $b_r$ , we define the (upper) exponential growth rate of all interfaces of $G$ :

\begin{equation*}b=b(G)\,:\!= \lim _{\epsilon \to 0} \limsup _{n\to \infty } c_{n}(G)^{1/n}\end{equation*}

where $c_{n}(G)\,:\!= |\{\text{ interfaces $P$ with $|P|=n$} \}|$ . In the following proposition, we prove that $b(G)=\max _r b_r(G)$ .

Observation 4.3. Let $G$ be a bounded degree graph. Then, there is some $r$ such that $b(G)= b_r(G)$ .

Proof. Notice that there are no (site)interfaces $P$ with $|\partial P|/|P|\gt \Delta$ , where $\Delta$ is the maximum degree of $G$ . Recursively subdivide the interval $I_0\,:\!= [0,\Delta ]$ into two subintervals of equal length. At each step $j$ , one of the two subintervals $I_j$ of $I_{j-1}$ accounts for at least half of the (site)interfaces $P$ of size $n$ with $|\partial P|/|P|\in I_{j-1}$ for infinitely many $n$ . Hence, there are at least $2^{-j} c_n$ (site)interfaces of size $n$ with $|\partial P|/|P|\in I_j$ for infinitely many $n$ . By compactness, $[0,\Delta ]$ contains an accumulation point $r_0$ of the $I_j, j\in{\mathbb N}$ . Notice that for every $\epsilon \gt 0$ , we have $\limsup _{n\to \infty } c_{n,r_0,\epsilon }^{1/n}=b$ . Taking the limit as $\epsilon$ goes to $0$ , we obtain $b= b_{r_0}$ , as desired.

Using Theorem 3.7, we can easily obtain some bounds for $b_r$ for graphs which either satisfy a $d$ -dimensional isometric inequality P3 or contain a quasi-geodesic P4. In what follows, we will write $N_n$ for the (random) number of occurring (site)interfaces $P$ with $|P|=n$ in a percolation configuration $\omega$ .

Proposition 4.4. Let $G$ be a graph satisfying P3 or P4 . Let $r\gt 0, 0\leq p\leq 1$ . Then, we have $p(1-p)^r \leq 1/b_r(G)$ .

Proof. Let us first assume that $G$ satisfies P4. Consider a quasi-geodesic $X$ containing $o$ , and let $X^+$ , $X^-$ be its two infinite subpaths starting from $o$ . Any occurring (site)interface $P$ has to contain a vertex $x^+$ in $X^+$ , and a vertex $x^-$ in $X^-$ ( $x^+$ and $x^-$ may possibly coincide). If $|P|=n$ , then $d_G(x^+,x^-)\leq n$ , because $P$ is a connected graph. Hence, $d_X(x^+,x^-)\leq \ell n$ , implying that $x^+$ is one of the first $ln+1$ vertices of $X^+$ . Since occurring (site)interfaces are disjoint by Theorem 3.7,

(5) \begin{align} N_n\leq \ell n+1 \end{align}

for every $n$ and any bond (site) percolation configuration $\omega$ . Therefore, $\mathbb{E}_p(N_n)\leq \ell n+1$ for every $p\in [0,1]$ . We now have $\ell n+1\geq \mathbb{E}_p(N_n)\geq c_{n,r,\epsilon } (p(1-p)^{r+\epsilon })^n$ . Taking the $n$ th root, and then letting $n$ go to infinity, and $\epsilon$ go to $0$ , we obtain $p(1-p)^r \leq 1/b_r$ , as desired.

If $G$ does not contain a quasi-geodesic but satisfies the isoperimetric inequality P3, then the assertion can be proved as follows. Since $G$ is locally finite, it contains an $1$ -way infinite path $X$ starting from $o$ that does not revisit the same vertex twice. Any occurring (site)interface $P$ has to contain one of the first $(|P|/c)^{\frac{d}{d-1}}$ vertices of $X$ by P3, hence $N_n\leq (n/c)^{\frac{d}{d-1}}$ . Arguing as above, we obtain $p(1-p)^r \leq 1/b_r$ .

Next, we observe that for any fixed $r$ , equality in Proposition 4.4 can occur for at most one value of $p$ , which value we can compute:

Proposition 4.5. Let $G$ be a graph satisfying P3 or P4 . If $p(1-p)^r = 1/b_r(G)$ for some $r,p$ , then $p=\frac 1{1+r}$ $\Big($ and so $r=\frac{1-p}{p}$ and $1/b_r(G)= p(1-p)^{\frac{1-p}{p}}\Big)$ .

Proof. Fix $r$ and let $M\,:\!= \max _{p\in [0,1]} p(1-p)^r$ . If $p_0(1-p_0)^r = 1/b_r$ is satisfied for some $p_0\in [0,1]$ , then $p_0$ must attain $M$ by Proposition 4.4, that is, we have $M= p_0(1-p_0)^r$ . Since the function $f(p)= p(1-p)^r$ vanishes at the endpoints $p=0,1$ , we deduce that $f^{\prime}(p_0)=0$ . By elementary calculus, $f^{\prime}(p)= (1-p)^r - rp(1-p)^{r-1}$ , from which we obtain $r= \frac{1-p_0}{p_0}$ and $p_0=\frac 1{1+r}$ .

Combining Proposition 4.4 and Proposition 4.5, we obtain

(6) \begin{equation} b_r \leq f(r)\,:\!= \frac{(1+r)^{1+r}}{r^r}. \end{equation}

Motivated by Proposition 4.5, we define the functions

\begin{equation*}p(r)\,:\!= \frac 1{1+r} \text { and } r(p)\,:\!= \frac {1-p}{p}.\end{equation*}

These functions are 1-1, strictly monotone decreasing and the inverse of each other.

Recall that $N_n$ denotes the number of occurring multi-interfaces $P$ with $|P|=n$ . The next result says that equality is achieved in Proposition 4.5 (for some $r$ ) exactly for those $p$ for which exponential decay in $n$ of $\mathbb E_p(N_n)$ fails.

Proposition 4.6. Let $G$ be a graph satisfying P3 or P4 and $p\in (0,1)$ . Then $\mathbb E_p(N_n)$ fails to decay exponentially in $n$ if and only if $b_{r(p)}(G) = 1/p(1-p)^{r(p)}$ (that is, if and only if equality is achieved in Proposition 4.5).

For the proof of this, we will make use of a large deviation bound for $\mathbb E_p(N_n)$ . In the percolation setup of Proposition 4.6, we denote by $N_{n,r(p),\epsilon }$ the (random) number of occurring (site)multi-interfaces $P$ with $|P|=n$ and $(r(p)-\epsilon )n \leq |\partial P| \leq (r(p)+\epsilon )n$ . The following lemma says that for any $p\in (0,1)$ , most occurring multi-interfaces have a volume-to-surface ratio close to the value $r(p)$ .

Lemma 4.7. Let $G$ be a graph satisfying P3 or P4 and $p\in (0,1)$ . For every $\epsilon \gt 0$ , there exists $\delta \gt 0$ such that $\mathbb E_p(N_n-N_{n,r(p),\epsilon })\leq e^{-\delta n}$ for every $n\in{\mathbb N}$ .

Proof. Consider the function $g(q,r)=q(1-q)^r$ . Notice that for every fixed $r$ , the function $g_r(q)\,:\!=g(q,r)$ is maximised at $\frac{1}{1+r}$ and is strictly monotone on the intervals $\big[0,\frac{1}{1+r}\big]$ and $\big[\frac{1}{1+r},1\big]$ . Recall that $p=\frac{1}{1+r(p)}$ , and define

\begin{equation*}s=s(p,\epsilon )\,:\!=\frac {1}{1+r(p)+\epsilon }\end{equation*}

and

\begin{equation*}S=S(p,\epsilon )\,:\!=\frac {1}{1+r(p)-\epsilon }.\end{equation*}

It follows that there is a constant $0\lt c=c(p,\epsilon )\lt 1$ such that $g(p,r(p)+\epsilon )\leq c g(s,r(p)+\epsilon )$ and $g(p,r(p)-\epsilon )\leq c g(S,r(p)-\epsilon )$ , because $s\lt p\lt S$ . Moreover, we have

\begin{equation*}\left (\frac {1-p}{1-s}\right )^r \leq \left (\frac {1-p}{1-s}\right )^{r(p)+\epsilon }\end{equation*}

whenever $r\geq r(p)+\epsilon$ , and

\begin{equation*}\left (\frac {1-p}{1-S}\right )^r \leq \left (\frac {1-p}{1-S}\right )^{r(p)-\epsilon }\end{equation*}

whenever $r\leq r(p)-\epsilon$ . This implies that $g(p,r)\leq c g(s,r)$ for every $r\geq r(p)+\epsilon$ , and $g(p,r)\leq c g(S,r)$ for every $r\leq r(p)-\epsilon$ . Summing over all possible (site)multi-interfaces $P$ with $|P|=n$ and $|\partial P|\gt (r+\epsilon )n$ or $|\partial P|\lt (r-\epsilon )n$ gives

\begin{equation*}\mathbb E_p\!\left(N_n-N_{n,r(p),\epsilon }\right)\leq c^n\!\left(\mathbb E_{s}(N_n)+\mathbb E_{S}(N_n)\right).\end{equation*}

Since both $\mathbb E_{s}(N_n),\mathbb E_{S}(N_n)\leq ln+1$ , we conclude that $\mathbb E_p(N_n-N_{n,r(p),\epsilon })$ decays exponentially in $n$ .

Proof of Proposition 4.6. For the backward implication, let $\varepsilon \gt 0$ and note that for every $n \geq 1$ we have

\begin{equation*} \mathbb E_p(N_n)\geq c_{n,r(p),\varepsilon } p^n (1-p)^{n(r(p)+\varepsilon )}. \end{equation*}

Taking $n$ -th roots and then sending $n$ to infinity and $\varepsilon$ to $0$ , we obtain that

\begin{equation*} \limsup _{n\to \infty }\mathbb E_p(N_n)^{1/n}\geq b_{r(p)}p (1-p)^{r(p)}. \end{equation*}

Thus, $\mathbb E_p(N_n)$ does not decay exponentially if $b_{r(p)}=1/p (1-p)^{r(p)}$ .

For the forward implication, suppose to the contrary that

\begin{equation*}b_{r(p)} \lt 1/p(1-p)^{r(p)}.\end{equation*}

The definition of $b_r$ implies that there are $\epsilon,\delta \gt 0$ such that

\begin{equation*}c_{n,r(p),\epsilon } p^n (1-p)^{n(r(p)-\epsilon )}\leq (1-\delta )^n\end{equation*}

for all but finitely $n$ . Hence for every large enough $n$ ,

\begin{equation*}\mathbb E_p(N_{n,r(p),\epsilon })\leq c_{n,r(p),\epsilon } p^n (1-p)^{n(r(p)-\epsilon )}\leq (1-\delta )^n,\end{equation*}

which implies the exponential decay in $n$ of $\mathbb E_p(N_{n,r(p),\epsilon })$ . On the other hand, $\mathbb E_p(N_n-N_{n,r(p),\epsilon })$ decays exponentially in $n$ by Lemma 4.7. Therefore, $\mathbb E_p(N_n)$ decays exponentially in $n$ too.

Let $S_o$ denote the (site)interface of the cluster $C_o$ of $o$ if $C_o$ is finite, and $S_o=\emptyset$ otherwise. We can now easily deduce that the statement of Proposition 4.6 holds for $P_p( |S_o|=n )$ in place of $\mathbb E_p(N_n)$ , as stated in Theorem 1.2, which we repeat here for convenience:

Theorem 4.8. Let $G\in \mathcal{S}$ . Then for every $p\in (0,1)$ , the cluster size distribution ${\mathbb{P}}_p( |S_o|=n )$ fails to decay exponentially in $n$ if and only if ¹

\begin{equation*}b_{r(p)}(G)= 1/p(1-p)^{r(p)} = f(r(p)).\end{equation*}

Proof. Let $X$ be a quasi-geodesic containing $o$ such that $X+tv_1=X$ for some $t\in{\mathbb N}$ , and let $X^+$ be one of the two infinite subpaths of $X$ starting at $o$ . Recall the definition of $\mathcal{S}$ in Definition 3.1. If $G$ is ${\mathbb{Z}}^d$ or $\mathbb{T}^d$ , we just let $X$ be a geodesic. Notice that any (site)interface $P$ meets $X^+$ at some vertex $x^+$ . Using a multiple $ktv_1$ of $tv_1$ for some integer $k$ , we can translate $x^+$ to one of the first $M$ vertices of $X^+$ , for some fixed $M\gt 0$ . It is not hard to see that $P+ktv_1$ is a (site) interface of $o$ , that is it still separates $o$ from infinity. On the event $A=A(P)\,:\!=\{\text{$P+ktv_1$ occurs}\} \cap \{\text{the subpath of $X^+$ between $o$ and $x^+ +ktv_1$ is open}\}$ , we have $S_o=P+ktv_1$ . Moreover,

\begin{equation*}p^M {\mathbb {P}}_p(P \text { occurs})\leq {\mathbb {P}}(A).\end{equation*}

Summing over all (site)interfaces of size $n$ with the property that the first vertex of $X^+$ they contain is $x^+$ , we obtain

\begin{equation*} p^M \sum {\mathbb {P}}_p(P \text { occurs})\leq {\mathbb {P}}_p( |S_o|=n ),\end{equation*}

where the sum ranges over all such (site)interfaces. Since there are at most $ln+1$ choices for the first vertex of $X^+$ , summing over all possible $x^+$ we obtain

\begin{equation*}p^M \mathbb {E}_p(N_n)\leq (ln+1){\mathbb {P}}_p( |S_o|=n ).\end{equation*}

On the other hand, clearly

\begin{equation*}{\mathbb {P}}_p( |S_o|=n )\leq \mathbb {E}_p(N_n).\end{equation*}

Therefore, ${\mathbb{P}}_p(|S_o|=n)$ decays exponentially if and only if $\mathbb E_p(X_n)$ does. The desired assertion follows now from Proposition 4.6.

5. Duality

The main aim of this section is the proof of Theorem 1.3 (Theorem 5.1) and an analogous statement for planar bond percolation (Theorem 5.2). In this section, we study the properties of both interfaces and site interfaces of graphs in $\mathcal{S}$ .

If $G\in \mathcal{S}$ satisfies (4), we say that $(P,\partial P)$ is a site inner interface of $G$ if $(\partial P,P)$ is a site interface of $G$ . In other words, any site inner interface can be obtained from an interface by exchanging the roles of occupied and vacant vertices. When clear from context, we will simply refer to $(P,\partial P)$ as an inner-interface.

Recall that for a site interface $(\partial P,P)$ , $\partial P$ spans a connected graph. We claim that when (4) is satisfied, then $P$ spans a connected graph too. Indeed, assume that this is not the case, and consider a set of vertices $C \subset P$ which spans a connected graph. Then, $(C,P\setminus C)$ is a proper bipartition of $P$ ; hence, there exist vertices $u\in C$ , $v \in P\setminus C$ which lie in the same triangle. In particular, $u$ and $v$ lie in the same connected component, which is a contradiction.

We define $b_r^*$ similarly to $b_r$ , except that we now count inner-interfaces instead of site interfaces. Since this operation inverts the surface-to-volume ratio, we have

(7) \begin{equation} b_r^*= b_{1/r}^r. \end{equation}

If $G$ is a doubly periodic planar lattice, we say that $(P,\partial P)$ is an inner-interface of $G$ if $(\partial P^*,P^*)$ is an interface of $G^*$ . Again define $b_r^*(G)$ similarly to $b_r(G)$ , except that we now count inner-interfaces in the dual lattice $G^*$ . Then (7) still holds in this case.

The main results of this section are:

Theorem 5.1. Consider a graph $G\in \mathcal{S}$ satisfying (4). Then for the site interfaces in $G$ we have $b_r(G)= (b_{1/r}(G))^r$ for every $r\gt 0$ .

Theorem 5.2. Consider a doubly periodic planar lattice $G$ . Then for the interfaces in $G$ and $G^*$ , we have $b_r(G)= (b_{1/r}(G^*))^r$ for every $r\gt 0$ .

To prove Theorems 5.1 and 5.2, we need the following concepts. Given a graph $G\in \mathcal{S}$ , let $v_1,v_2,\ldots, v_d\in{\mathbb{R}}^d$ be some linearly independent vectors that preserve $G$ , and let $\mathcal{B}$ be the box determined by $v_1,v_2,\ldots,v_d$ . For ${\mathbb{Z}}^d$ and $\mathbb{T}^d$ we can choose $v_1,v_2,\ldots v_d$ to be the standard basis of ${\mathbb{R}}^d$ . Given a (site)interface $P$ of $G$ , let $\mathcal{T}$ be the set of translations $\mathcal{B}+k_1v_1+k_2v_2+\ldots k_dv_d$ , $k_1,k_2,\ldots,k_d \in \mathbb{Z}$ of $\mathcal{B}$ that intersect $P\cup \partial P$ . The box $B(P)$ of $P$ is the smallest box with sides parallel to $v_1,v_2,\ldots,v_d$ containing $\mathcal{T}$ . We write $|B(P)|$ for the surface area of $B(P)$ , and we call it the box size of $P$ .

For every $n\in{\mathbb N}$ , $r \in{\mathbb{R}}_+$ , $\epsilon \in{\mathbb{R}}_+$ , and $\delta \in{\mathbb{R}}_+$ let $c_{n,r,\epsilon,\delta }(G)$ denote the number of interfaces $P$ with $|P|=n$ , $(r-\epsilon )n \leq |\partial P| \leq (r+\epsilon )n$ and $|B(P)|\leq \delta n$ . We define $\widetilde b_r$ to be the exponential growth rate as $\delta \to 0$ and $\epsilon \to 0$ :

\begin{equation*}\widetilde {b_r}=\widetilde {b_r}(G)\,:\!= \lim _{\epsilon \to 0} \lim _{\delta \to 0}\limsup _{n\to \infty } {c_{n,r,\epsilon,\delta }(G)}^{1/n}.\end{equation*}

Our aim now is to prove that $\widetilde b_r = b_r$ . In other words, (site)interfaces with a ‘fractal’ shape have the same exponential growth rate as all (site)interfaces.

We will first consider the cases of ${\mathbb{Z}}^d$ and $\mathbb{T}^d$ .

Proposition 5.3. Let $G$ be either ${\mathbb{Z}}^d$ or $\mathbb{T}^d$ . Then $\widetilde b_r(G) = b_r(G)$ .

Proof. Let us start with an informal outline of the proof. We consider a big box which we partition by boxes $B_{\textbf{i}}$ of much smaller size chosen in a suitable way, and inside each box $B_{\textbf{i}}$ we place an interface of surface-to-volume ratio roughly $r$ whose box is $B_{\textbf{i}}$ . To handle the combinatorial complexity of the set of interfaces we wish to construct, we need to choose $B_{\textbf{i}}$ so that it is the box of a big proportion of interfaces. Connecting all interfaces in a suitable way, they merge into a larger interface which has a ‘fractal’ shape. However, to show that the surface-to-volume ratio of the interface we constructed is roughly $r$ , we need to connect all the interfaces by short paths. To this end, we move around each box $B_{\textbf{i}}$ so that interfaces in neighbouring boxes can be connected by short paths.

We now proceed with the formal proof. We will first prove the assertion for interfaces. Let us first assume that $b_r\gt 1$ . Let $n\in{\mathbb N}$ , $\epsilon \gt 0$ , $r\gt 0$ , and let $P\in I_{n,r,\epsilon }$ . Consider the box $B(P)$ and notice that it contains $P\cup \partial P$ in its interior (no vertex of $P\cup \partial P$ lies in its topological boundary). Order the vertices on the boundary of the box arbitrarily. Define the shape of an interface $P$ to be the $3d$ -tuple consisting of the dimensions of the box $B(P)$ , and the first vertex of each of the $2d$ faces of $B(P)$ in our ordering that has distance $1$ from $\partial P$ . We will call these vertices extremal. Notice that the extremal vertices are incident to a vertex in $\partial ^V P$ .

We start by showing that there is a set $K\subset I_{n,r,\epsilon }$ that has the same growth rate as $I_{n,r,\epsilon }$ and which consists of interfaces of the same shape. Indeed, notice that each side of $B(P)$ has at most $n+4$ vertices because the diameter of $P$ is at most $n$ . Once we know the box of $P$ , there are at most $(n+4)^{2d(d-1)}$ possibilities for the extremal vertices; hence, there are at most $q(n)\,:\!=(n+4)^{2d^2}$ possible shapes for interfaces of size $n$ . On the other hand, there are exponentially many interfaces in $I_{n,r,\epsilon }$ , so we can choose $n$ large enough to ensure that there is a non-empty set $K\subseteq I_{n,r,\epsilon }$ of cardinality at least

\begin{equation*}N\,:\!=c_{n,r,\epsilon }/q(n)\end{equation*}

consisting of interfaces $P$ with $|P|=n$ and $(r-\epsilon )n \leq |\partial P| \leq (r+\epsilon )n$ that have the same shape.

With the set $K$ in our disposal, we will now describe how to piece elements of $K$ together to construct several interfaces of small box size and surface-to-volume ratio which is approximately $r$ .

Recall that all interfaces in $K$ have the same shape, in particular, the same box $\mathcal{B}$ . Let $B_n$ be a $d$ -dimensional grid of $n^{d(d-1)}$ adjacent copies $B_{\textbf{i}}$ , $\textbf{i}=(i_1,\ldots,i_d)$ of $B$ (each side contains $n^{d-1}$ copies of $B$ ). In each copy of $B$ in $B_n$ , we place an arbitrary element of $K$ . We denote the element of $K$ placed in $B_{\textbf{i}}$ with $K_{\textbf{i}}$ . Write $S_k$ , $1\leq k\leq n^{d-1}$ for the slab containing the boxes $B_{\textbf{i}}$ with $i_1=k$ . Our aim is to connect the interfaces inside the boxes using mostly short paths. First, consider $S_2$ and notice that every box in $S_2$ shares a common face with a box in $S_1$ . We can move $S_2$ using the vectors $v_2,\ldots,v_d$ in order to achieve that the ‘rightmost’ extremal vertices of $S_1$ coincide with the corresponding ‘leftmost’ extremal vertices of $S_2$ lying in a common face with them. This is possible because all interfaces in $K$ have the same shape. Moving each slab $S_k$ in turn, we can make the ‘rightmost’ and ‘leftmost’ extremal vertices of consecutive slabs coincide. We now connect all these extremal vertices with their corresponding interfaces by attaching paths of length two parallel to $v_1$ . Finally, we connect the interfaces in the first slab as follows. If two boxes in the first slab share a common face, then we connect the two extremal vertices lying in the common face with a path of minimum length inside that face (hence of length $O(n)$ ). Also, we attach a path of length two connecting all those extremal vertices to the interface of their box (Figure 3).

Figure 3. The interface $Q$ is in the proof of Proposition 5.3.

This construction defines a new graph $Q$ . We claim that $Q$ is an interface. Indeed, if $d=2$ it is not hard to see that each edge of $Q$ is incident to the unbounded face of $Q$ because of the way $Q$ is constructed and the fact that each $K_{\textbf{i}}$ has by definition the property that all its edges lie in the unbounded component of $K_{\textbf{i}}$ . It follows that $Q$ is an interface.

For $d\gt 2$ , since $Q$ is a connected graph, there is a unique interface $I$ associated with it given by Theorem 3.7. We will prove that $Q$ coincides with $I$ by determining $\partial I$ . We will show this in several steps. Let $V_{\textbf{i}}$ be the set of edges in $G$ that are perpendicular to some edge in $E_{\textbf{i}}\,:\!=\partial K_{\textbf{i}}\cap Q$ . Note that any edge in $V_{\textbf{i}}$ can be connected to infinity without vising $\partial _E Q$ because of the way $Q$ is constructed. Since $\partial I$ separates $Q$ from infinity, it follows that $V_{\textbf{i}}\subset \partial I$ .

Next we will use this fact to show that $C_{\textbf{i}}\,:\!=(\partial K_{\textbf{i}}\setminus Q)\cup V_i$ is contained in $\partial I$ . It suffices to show that $\vec{C_{\textbf{i}}^{Q}}$ is $C_{\textbf{i}}$ -connected, since then $C_{\textbf{i}}\cup \partial I$ satisfies property (iii) and the uniqueness in Theorem 3.7 implies that $C_{\textbf{i}}\cup \partial I=\partial I$ . To this end, consider a directed edge $\vec{e}$ in $\vec{\partial K_{\textbf{i}}^{K_{\textbf{i}}}}$ that can be connected to $\vec{f}\in{\vec{E_{\textbf{i}}^{K_{\textbf{i}}}}}$ with a $\mathcal{P}$ -path $\Pi$ in $G\setminus \partial K_{\textbf{i}}$ . In the case of ${\mathbb{Z}}^d$ , extending $\Pi$ by $\vec{f}$ we obtain a $\mathcal{P}$ -path connecting $\vec{e}$ to $V_{\textbf{i}}$ . If $\vec{e}$ is a diagonal edge of $\mathbb{T}^d$ , then extending $\Pi$ by $\vec{f}$ we obtain a $\mathcal{P}$ -path connecting $\vec{e}$ to $\overleftarrow{e}$ (in this case both end vertices of $\vec{e}$ belong to $Q$ ). Now $\overleftarrow{e}$ can be connected to $V_{\textbf{i}}$ with the trivial path of length $0$ . Similarly, if $\vec{e}$ is a non-diagonal edge of $\mathbb{T}^d$ , then $\vec{e}$ can be connected to $V_{\textbf{i}}$ by concatenating two $\mathcal{P}$ -paths. Using these observations we see that for any non-trivial bipartition $(J,C_{\textbf{i}}\setminus J)$ of $C_{\textbf{i}}$ there is a $\mathcal{P}$ -path in $G\setminus C_{\textbf{i}}$ connecting $J$ to $C_{\textbf{i}}\setminus J$ . This shows that $\vec{C_{\textbf{i}}^{Q}}$ is $C_{\textbf{i}}$ -connected, as desired.

It now follows from property (ii) that $K_{\textbf{i}}\subset I$ . Since $I$ is connected and there is a unique path connecting different $K_{\textbf{i}}$ in neighbouring boxes, the latter paths need to lie in $I$ . Thus $Q\subset I$ , which implies that $Q=I$ , that is $Q$ is an interface.

It can be easily seen that $Q$ has size roughly $n^{d(d-1)+1}$ and boundary size

\begin{equation*}(r-\epsilon ^{\prime})|Q|\leq |\partial Q |\leq (r+\epsilon ^{\prime})|Q|\end{equation*}

for some $\epsilon ^{\prime}=\epsilon ^{\prime}(n)$ not necessarily equal to $\epsilon$ . Clearly, we can choose $\epsilon ^{\prime}=\epsilon +o(1)$ , since the number of attached edges is $O(n^d)$ . The number of such $Q$ we construct is $|K|^{n^{d(d-1)}}\geq N^{n^{d(d-1)}}$ , because by deleting all attached paths we recover all $K_{\textbf{i}}$ , and we have $|K|$ choices for each $K_{\textbf{i}}$ .

Note that each slab $S_k$ has been moved at distance at most $(k-1)n=O(n^d)$ from its original position. Hence, $|B(Q)|=O(n^{d(d-1)})=o(|Q|)$ . The result follows by letting $n \to \infty$ and then $\epsilon \to 0$ .

It remains to consider the case where $b_r=0$ or $b_r=1$ . If $b_r=0$ , there is nothing to prove. If $b_r=1$ , then we can argue as in the case $b_r\gt 1$ , except that now we place the same interface at each box of the grid.

Let us now consider the case of site interfaces. Let us focus on the case $b_r\gt 1$ . Let $K$ be a collection of at least $N$ site interfaces of $I_{n,r,\epsilon }$ , all of which have the same shape. Arguing as above, we place the elements of $K$ in a $d$ -dimensional grid and we connect them in the same fashion to obtain a graph $Q$ . For ${\mathbb{Z}}^d$ nothing changes, since $Q$ is an induced graph. However, this is not necessarily true for $\mathbb{T}^d$ because some end vertices of the attached paths are possibly incident to multiple vertices of the same site interface (even the paths of the first slab are not induced). This could potentially lead to an issue in the case that some boundary vertices cannot connect to infinity without intersecting the vertices of $Q$ .

But this is impossible in our case. Indeed, define $B^{\prime}_{\textbf{i}}$ and $B^{\prime\prime}_{\textbf{i}}$ to be the smallest boxes containing $K_{\textbf{i}}$ and $K_{\textbf{i}} \cup \partial K_{\textbf{i}}$ , respectively. Notice that every face of $B^{\prime\prime}_{\textbf{i}}$ contains at most one vertex of $Q$ . Hence, no boundary vertex of $K_{\textbf{i}}$ lying in some face of $B^{\prime}_{\textbf{i}}$ can be separated from infinity by the vertices of $Q$ . Since any boundary vertex of $K_{\textbf{i}}$ can be connected in $G\setminus K_{\textbf{i}}$ to the boundary of $B^{\prime}_{\textbf{i}}$ by Proposition 3.9, the claim follows. Thus, the graph spanned by $Q$ is a site interface, which proves that $\widetilde b_r=b_r$ for site interfaces as well.

The above arguments can be carried out for interfaces of any doubly periodic planar lattice with only minor modifications that we will describe in Lemma 5.6. However, certain difficulties arise when studying site interfaces on an arbitrary doubly periodic planar lattice. Indeed, when we connect two site interfaces $P_1,P_2$ with a path, it is possible that some of the vertices of $\partial P_1$ or $\partial P_2$ are now ‘separated’ from the remaining boundary vertices, see Figure 4. In fact, it is possible that most boundary vertices have this property. To remedy this, instead of choosing arbitrarily the path that connects $P_1$ and $P_2$ , we will choose it appropriately so that only a few of them, if any, are ‘separated’ from the remaining boundary vertices.

Figure 4. If the vertex incident to the two dashed lines is attached to the site interface, the vertices of which are depicted with big disks, then the new graph is not a site interface any more.

Lemma 5.4. Let $G$ be a graph satisfying P3 for some $c\gt 0,d\geq 2$ . Assume that ${\mathcal{C}}(G)$ admits a basis consisting of cycles whose length is bounded by some $t\gt 0$ . Let $P$ be a site interface of $G$ . Then there are $|\partial ^V P|-O\big(|P|^{1/4}\big)=\Omega \left(|P|^{\frac{d-1}{d}}\right)$ vertices $u\in \partial ^V P$ such that the site interface of $P\cup \{u\}$ has size $|P|-O(|P|^{3/4})$ and boundary size $|\partial P|-O\big(|\partial P|^{3/4}\big)$ .

Proof. For every $v\in \partial ^V P$ , let $P_v$ be the site interface of the connected graph $P\cup \{v\}$ and let $Q_v\,:\!=\partial P \setminus (\partial P_v \cup \{v\})$ . Write $L$ for the edges with one endpoint in $P$ and the other in $\partial P$ , $E_v$ for the edges of the form $vw$ , $w\in P$ , and $L_v$ for the edges with one end vertex in $P$ and the other in $Q_v$ , see Figure 5. First, we claim that the $Q_v$ are pairwise disjoint. Indeed, assuming that this is not true, we find a pair of distinct $u,v$ such that $Q_u\cap Q_v \neq \emptyset$ . Since the vertices of $Q_z$ , $z\in \{u,v\}$ do not belong to $\partial P_z$ , $\vec{E_{z}^{{P}}}$ separates $\vec{L_{z}^{{P}}}$ from the remaining edges of $\vec{L^{{P}}}$ . Hence no vertex of $Q_z$ lies in $\partial ^V P$ , as any path starting from a vertex of $Q_z$ and going to infinity without intersecting $P$ must intersect $z$ . This implies that if $X,Y$ are two overlapping components of $\vec{L_{u}^{{P}}}$ , $\vec{L_{u}^{{P}}}$ , respectively, then $X\cup Y$ is $L\setminus (E_u\cup E_v)$ -connected, and thus $X,Y$ coincide. Moreover, $X$ is connected to $\vec{E_{u}^{{P}}}$ with a $\mathcal{P}$ -path in $G\setminus L$ , and $Y$ is connected to $\vec{E_{v}^{{P}}}$ with a $\mathcal{P}$ -path in $G\setminus L$ . Therefore, $u$ coincides with $v$ , which is absurd. Hence, our claim is proved.

Figure 5. The situation is in the proof of Lemma 5.4.

We can now conclude that $\sum _{v\in \partial ^V P} |Q_v|\leq |\partial P|\leq \Delta |P|$ , where $\Delta$ is the maximal degree of $G$ . It follows that the number of $v\in \partial ^V P$ such that $|Q_v|\geq |P|^{3/4}$ is at most $\Delta |P|^{1/4}$ . By the isoperimetric inequality P3 there is $c\gt 0$ such that $|\partial ^V P|\geq c |P|^{\frac{d-1}{d}}$ , which implies the strict inequality $|\partial ^V P|\gt \Delta |P|^{1/4}$ whenever $|P|$ is large enough. It is clear that $P_u$ has size $|P|-O(|P|^{3/4})$ , because $|P\setminus P_u|\leq \Delta ^t |Q_u|$ . The proof is now complete.

The boundary vertices satisfying the property of Lemma 5.4 will be called good, and the remaining ones will be called bad.

The following lemma will be used to handle the case of site interfaces in the case of doubly periodic planar lattices.

Lemma 5.5. Let $G$ be a doubly periodic planar lattice. Let $P$ be a site interface of size $n$ in $G$ , and $F\subset \partial ^V P$ . Assume that the site interface of $P\cup F$ has size at least $n-O(n^{3/4})$ . Then the number of site interfaces $P^{\prime}$ of size $n$ such that the site interfaces of $P\cup F$ and $P^{\prime}\cup F$ coincide, is $n^{O(n^{3/4})}$ .

Proof. Consider a site interface $P^{\prime}$ of size $n$ such that the site interface $X$ of $P\cup F$ , and the site interface of $P^{\prime}\cup F$ coincide. Let $k$ be the size of $P^{\prime}\setminus X$ . By our assumption, $k=O(n^{3/4})$ . Each connected component of $P^{\prime}\setminus X$ is incident to some vertex of $P$ ; hence, every vertex of $P^{\prime}\setminus X$ has distance $O(n^{3/4})$ from $P$ . By the polynomial growth of $G$ , the number of vertices at distance $O(n^{3/4})$ from $P$ is at most $m$ for some $m=O(n^{3/2})$ . There are

\begin{equation*}{\bigg(\begin{array}{l}m \\ k\end{array}\bigg)}\leq m^k =n^{O(n^{3/4})}\end{equation*}

subsets of size $k$ containing vertices having distance at most $k$ from $P$ . Therefore, there are $n^{O(n^{3/4})}$ site interfaces $P^{\prime}$ as above.

In order to generalise Proposition 5.3 to all elements of $\mathcal{S}$ , we will need the following definitions. Consider a doubly periodic planar lattice $G$ . Given two linearly independent vectors $z,w\in{\mathbb{R}}^2$ , we write $B(z,w)$ for the box determined by $z$ and $w$ . Given a side $s$ of $B(z,w)$ , we write $B^s(z,w)$ for the box that is congruent to $B(z,w)$ and satisfies $B^s(z,w)\cap B(z,w)=s$ . It is not hard to see that there are vectors $z_1,z_2,w_1,w_2$ such that the following hold:

• Both $z_1,w_1$ are parallel to $v_1$ , and both $z_2,w_2$ are parallel to $u_2$ .

• For every side $s$ of $B(z_1,z_2)$ , there are vertices $u\in B(z_1,z_2)$ and $v\in B^s(z_1,z_2)$ that can be connected with a path lying in $B(z_1,z_2)\cup B^s(z_1,z_2)$ .

• For every pair of vertices $u,v$ in $B(z_1,z_2)$ , there is a path in $B(w_1,w_2)$ connecting $u$ to $v$ .

We regard the tillings $\mathcal{T}_z$ and $\mathcal{T}_w$ of ${\mathbb{R}}^2$ by translates of $B(z_1,z_2)$ and $B(w_1,w_2)$ , respectively, as graphs that are naturally isomorphic to ${\mathbb{Z}}^2$ .

Lemma 5.6. Consider a graph $G\in \mathcal{S}$ . Then $\widetilde b_r(G) = b_r(G)$ .

Proof. We handled ${\mathbb{Z}}^d$ and $\mathbb{T}^d$ above, so it only remains to handle doubly periodic planar lattices. We will focus on the case of site interfaces with surface-to-volume ratio $r$ such that $b_r\gt 1$ , which is the hardest one.

Let $n\in{\mathbb N}$ , $\epsilon \gt 0$ , $r\gt 0$ , and let $P\in I_{n,r,\epsilon }$ . Recall that there is a $t\gt 0$ such that the cycles in our basis of ${\mathcal{C}}(G)$ have length at most $t$ . Consider the set of boxes in $\mathcal{T}_w$ that either intersect the $2t$ -neighbourhood of $P\cup \partial P$ , or they share a common face with such a box. Let $B^t(P)$ be the smallest box with sides parallel to $w_1,w_2$ containing all these boxes. Write $s$ for a side of $B^t(P)$ . Order the vertices of $B^t(P)$ arbitrarily. Among all vertices of $\partial ^V P$ that are closest to $s$ , there is one that is minimal. The minimal vertices associated with the sides of $B^t(P)$ are called extremal. Each extremal vertex lies in some box of $\mathcal{T}_z$ that is called extremal as well (in case a vertex lies in more than one boxes of $T_z$ , order the boxes arbitrarily and choose the minimal one). We define the shape of a site interface $P$ to be the tuple comprising the dimensions of the box $B^t(P)$ , and the extremal vertices of $P\cup \partial P$ . Using the polynomial growth of $G$ , we immediately deduce that we have polynomially many choices $q(n)$ for the shape and auxiliary shape of any site interface $P$ . We define $K$ as in the proof of Proposition 5.3.

By definition, all elements $P$ of $K$ have the same $B^t=B^t(P)$ . It is not hard to see that at least one of the two dimensions of $B^t$ is $\Omega (\sqrt{n})$ . Indeed, for every vertex $u$ of $G$ there is a disk of small enough radius $r_u\gt 0$ containing no other vertex except for $u$ . The translation invariance of $G$ implies that there are only finitely possibilities for $r_u$ , hence $r=\inf _{u\in V} r_u\gt 0$ . It follows that $B^t$ has area $\Omega (n)$ because it contains $n$ disjoint disks of radius $r$ . This implies that at least one of the two dimensions of $B^t$ is $\Omega (\sqrt{n})$ . We can assume without loss of generality that the dimension parallel to $v_1$ has this property.

We start with a $n\times n$ grid of copies $B_{i,j}$ of $B^t$ . We place inside every $B_{i,j}$ a site interface $K_{i,j}\in K$ . We write $S_k$ for the $k$ th column of the grid. Similarly to the proof of Proposition 5.3, we move every column, except for the first one, in the direction parallel to $v_2$ in such a way that the ‘rightmost’ extremal boxes of $S_k$ and the ‘leftmost’ extremal boxes of $S_{k+1}$ can be connected in $\mathcal{T}_z$ by a straight path parallel to $v_1$ .

For every pair $K_{i,j}$ , $K_{i,j+1}$ of consecutive interfaces, there is an induced path in $G$ of bounded length connecting their ‘rightmost’ and ‘leftmost’ extremal vertices. We can further assume that the path lies in $B_{i,j}\cup B_{i,j+1}$ by our choice of $z_1,z_2,w_1,w_2$ and the definition of $B^t$ . Indeed, if $\Pi =B_1,B_2,\ldots,B_l$ is a straight path in $\mathcal{T}_z$ connecting the ‘rightmost’ and ‘leftmost’ extremal boxes of $K_{i,j}$ , $K_{i,j+1}$ , respectively, we first connect all consecutive boxes $B_m,B_{m+1}$ , $m=1,\ldots,l-1$ using paths $\Pi _m$ in $G$ lying in $B_m\cup B_{m+1}$ . Then we connect the ‘rightmost’ and ‘leftmost’ end vertices of consecutive paths $\Pi _m$ , $\Pi _{m+1}$ , respectively, using paths lying in boxes congruent to $B(w_1,w_2)$ containing those end vertices. Finally, we connect the ‘rightmost’ and ‘leftmost’ of $K_{i,j}$ , $K_{i,j+1}$ to $P_1$ and $P_{l-1}$ using paths lying in boxes congruent to $B(w_1,w_2)$ . In this way, we obtain a path that lies in $B_{i,j}\cup B_{i,j+1}$ , because both $B_{i,j}$ , $B_{i,j+1}$ contain a ‘layer’ of boxes of $T_w$ surrounding $K_{i,j}$ , $K_{i,j+1}$ . The path is not necessarily disjoint from $K_{i,j}$ , $K_{i,j+1}$ but it certainly contains a subpath that is disjoint from them, and connects two boundary vertices of both site interfaces. We can choose the subpath to contain exactly two boundary vertices, one from each of the two site interfaces.

Let $\mathcal{W}$ be the path connecting $K_{i,j}$ , $K_{i,j+1}$ , and let $u_1\in \partial ^V K_{i,j}$ , $u_2\in \partial ^V K_{i,j+1}$ be the end vertices of $\mathcal{W}$ . Adding $u_1,u_2$ to $K_{i,j}$ , $K_{i,j+1}$ may result to much smaller site interfaces. For this reason, we need to find two good boundary vertices. Consider the vertices $x_1,x_2$ at distance $t$ from $u_1,u_2$ , respectively, lying in $\mathcal{W}$ . Write $Q_1,Q_2$ for the $(t-1)$ -neighbourhood of $K_{i,j}$ , $K_{i,j+1}$ , respectively, and notice that both $\partial ^V Q_1$ , $\partial ^V Q_2$ have distance $t$ from $\partial K_{i,j}$ , $\partial K_{i,j+1}$ , respectively. Furthermore, they coincide with the boundary of some site interface, that is the site interface of the finite connected component of their complement, and by Remark 3.8 we can connect any pair of vertices of $\partial ^V Q_i$ , $i=1,2$ with a path lying in the $t/2$ neighbourhood of $\partial ^V Q_i$ , hence disjoint from $K_{i,j}$ , $K_{i,j+1}$ and their boundaries. The isoperimetric inequality P3 gives $\partial ^V Q_i=\Omega (\sqrt{n})$ . Moreover, for every $k\gt 0$ , the number of vertices of $\partial ^V Q_i$ that can be connected to $x_i$ with a path of length at most $k$ lying in the $t/2$ -neighbourhood of $\partial ^V Q_i$ is $\Omega (k)$ . On the other hand, Lemma 5.4 implies that $O(n^{1/4})$ boundary vertices of either $K_{i,j},K_{i,j+1}$ are bad. Hence choosing $k=cn^{1/4}$ for some large enough constant $c\gt 0$ , we can find two good vertices $y_1,y_2$ in $\partial ^V K_{i,j},\partial ^V K_{i,j+1}$ , that can be connected to $x_1,x_2$ , respectively, in the following way: we first connect $y_i$ to some vertex of $\partial ^V Q_i$ with a path of length $t$ , and then we connect the latter vertex with a path of length $O(n^{1/4})$ lying in the $t/2$ neighbourhood of $\partial ^V Q_i$ . Taking the union of these two paths with the subpath of $\mathcal{W}$ connecting $x_1$ to $x_2$ , we obtain a path of length $O(n^{1/4})$ connecting $y_1$ to $y_2$ that lies in $B_{i,j}\cup B_{i,j+1}$ . We attach this path to our collection of site interfaces.

Consider now a site interface $K_{i,j}$ with $2\leq j\leq n-1$ . Notice that exactly two paths emanate from $\partial K_{i,j}$ , one of which has distance $O(n^{1/4})$ from the ‘rightmost’ extremal vertex of $K_{i,j}$ , and the other has distance $O(n^{1/4})$ from the ‘leftmost’ extremal vertex of $K_{i,j}$ . The two paths may possibly overlap, separating some vertices of $\partial K_{i,j}$ from infinity. However, the distance between the ‘rightmost’ and the ‘leftmost’ extremal vertex is $\Omega (\sqrt{n})$ because the dimension of $B_{i,j}$ that is parallel to $v_1$ is $\Omega (\sqrt{n})$ . We can increase the value of $n$ if necessary to ensure that the paths do not overlap.

Moreover, we connect, as we may, the boundaries of consecutive site interfaces $K_{i,1},K_{i+1,1}$ of the first column with induced paths of length $O(n)$ disjoint from any other site interface, only the end vertices of which intersect the boundary of $K_{i,1},K_{i+1,1}$ .

In this way, we obtain a graph $H$ containing all site interfaces $K_{i,j}$ . Consider the graph spanned by $H$ , and let $Q$ be the site interface of this induced graph. We claim that $Q$ has size $n^3(1-o(1))$ , and boundary size between $(r-\epsilon ^{\prime})|Q|$ and $(r+\epsilon ^{\prime})|Q|$ , for some $\epsilon ^{\prime}=\epsilon +o(1)$ . Indeed, for every site interface $K_{i,j}$ that does not lie in the first column, if $F_{i,j}\subset \partial K_{i,j}$ is the set of end vertices of the attached paths that emanate from $\partial K_{i,j}$ , then the site interface of $K_{i,j}\cup F_{i,j}$ (which has size $n-O(n^{1/4})$ ) lies in the boundary of $Q$ . Since we have $n^2-n$ such $K_{i,j}$ , the claim follows readily.

Each column $S_k$ has been moved at distance $O(kn)=O(n^2)=o(|Q|)$ from its original position. Hence $|B(Q)|=o(|Q|)$ . It remains to show that the number of such $Q$ constructed is roughly $N^{n^2}$ . Notice that we have not necessarily used the same paths to connect our interfaces, and so given such a $Q$ , we cannot immediately recover all possible sequences $(K_{i,j})$ giving rise to $Q$ . Our goal is to restrict to a suitable subfamily of $K^{n^2}$ .

We claim that there are only subexponentially many in $n^3$ possibilities for the attached paths. Recall that all elements of $K$ have the same extremal vertices. The end vertices of every attached path have distance $O(n^{1/4})$ from a pair of extremal vertices. Using the polynomial growth of $G$ , we conclude that there are only polynomially many choices in $n$ for each end vertex. Moreover, the paths connecting interfaces of the first column have length $O(n)$ , and the remaining paths have length $O(n^{1/4})$ . There are at most $\Delta ^{O(n)}$ choices for each path connecting site interfaces of the first column, and at most $\Delta ^{O(n^{1/4})}$ choices for each of the remaining paths, because any path starting from a fixed vertex can be constructed sequentially, and there are at most $\Delta$ choices at each step. In total, there are $\Delta ^{O(n^{9/4})}$ possibilities for the attached paths. This proves our claim.

On the other hand, there are at least $N^{n^2}$ sequences $(K_{i,j})\in K^{n^2}$ , hence for a subfamily of $K^{n^2}$ of size at least $N^{n^2}/{\Delta ^{O(n^{9/4})}}$ , we have used exactly the same paths. Let us restrict to that subfamily. Since we have fixed the paths connecting the elements of the subfamily, given some $Q$ constructed by the elements of that subfamily, we can now delete every vertex of the attached paths except for their end vertices to ‘almost’ reconstruct all site interfaces producing $Q$ . To be more precise, if $(K_{i,j})$ and $(K^{\prime}_{i,j})$ are two sequences producing the same $Q$ , then the site interfaces of $K_{i,j}\cup F_{i,j}$ and $K^{\prime}_{i,j}\cup F_{i,j}$ coincide. By Lemma 5.5, if we fix a sequence $(K_{i,j})$ producing $Q$ , then for each $i,j$ with $j\gt 1$ , there are subexponentially many in $n$ possible $K^{\prime}_{i,j}$ as above. For each of the remaining $i,j$ there are at most exponentially many in $n$ $K^{\prime}_{i,j}$ as above, since there are at most exponentially many site interfaces in total. Therefore, each $Q$ can be constructed by subexponentially many in $n^3$ sequences. We can now deduce that we constructed roughly $N^{n^2}$ $Q$ , and taking limits we obtain $\widetilde b_r = b_r$ , as desired.

We can now prove the main results of this section.

Proof of Theorem 5.1 . Assume first that both $b_r$ and $b_{1/r}$ are not $0$ . We start by proving that

(8) \begin{equation} b_r^*\geq b_r. \end{equation}

Combined with (7) this will easily yield the desired equality.

Assume that $G$ is a doubly periodic planar lattice. Let $n\in{\mathbb N}$ , $r\gt 0$ , $\epsilon \gt 0$ , and choose $P\in I_{n,r,\epsilon }$ . By Proposition 5.6, we may assume that $P$ satisfies $|B(P)| = o(|P|)=o(n)$ . Recall that $B(P)$ contains $P\cup \partial P$ in its interior. It is not hard to see that there is a cycle $C$ at bounded distance from $P$ that separates $B(P)$ from infinity and has size $O(|B(P)|)$ . Arguing as in the proof of Lemma 5.6 we find a good vertex $u\in \partial ^V P$ , and an induced path $\Pi$ connecting $u$ to $C$ that has size $O(n^{1/4})$ , and does not contain any other vertex of $P\cup \partial P$ .

Figure 6. The vertices of $Q$ are depicted with big disks, and the vertices of $\partial Q$ are depicted with smaller disks. The edges spanned by $P$ and $C$ are depicted in solid lines, while the edges of $\Pi$ are depicted in dashed lines.

Our aim now is to find a suitable inner-interface containing the site interface of $P\cup \{u\}$ , which we denote by $X$ . Since the cycle space of $G$ is generated by its triangles, $\partial ^V P$ spans a cycle surrounding $P$ and the remaining boundary vertices. Hence $\partial ^V P \setminus \{u\}$ spans a connected graph. The graph $\Gamma \,:\!=X\cup \Pi \cup C$ surrounds an open subset of the plane that contains $\partial ^V P \setminus \{u\}$ . Consider the connected component $Y$ of $\partial ^V P \setminus \{u\}$ in this open set. Write $Q$ for the inner-interface of $Y$ , that is the boundary of the site interface of $Y$ , see Figure 6.

We claim that $Q$ contains $X$ and is contained in $X\cup \Pi \cup C$ . To see that $Q$ contains $X$ , notice that all vertices of $X$ are incident to $Y$ because $G$ is a triangulation, and lie in the external face of $Y$ . Therefore, $X$ is contained in $Q$ . Moreover, if $Q$ contains some vertex not in $X\cup \Pi \cup C$ , then we can add this vertex to $Y$ to obtain an even larger connected graph. This contradiction shows that there is no such vertex and proves our claim.

We now consider the case where $G=\mathbb{T}^d$ . We can let $C$ be the set of vertices in the boundary of $B(P)$ , and $\Pi$ be a path of length $2$ connecting an extremal vertex of $B(P)$ to $P$ . Let $Y$ be the subgraph of $G$ surrounded by $P\cup \Pi \cup \partial C$ . It is clear that $Y$ is connected. Write $Q$ for the inner-interface of $Y$ . Every vertex of $P$ is incident to $Y$ and lies in the infinite component of $G\setminus Y$ . Hence $P$ lies in $Q$ . Furthermore, $Q$ contains only vertices of $X\cup \Pi \cup \partial C$ .

In both cases, $Q$ has roughly $n$ vertices and surface-to-volume ratio between $(r-\epsilon ^{\prime})|Q|$ and $(r+\epsilon ^{\prime})|Q|$ for some $\epsilon ^{\prime}=\epsilon +o(1)$ . Moreover, each $Q$ can be obtained from only subexponentially many $P$ . This proves (8). Combining this with (7), we obtain the following:

\begin{equation*}b_r^*\geq b_r = \left(b^*_{1/r}\right)^r \geq b_{1/r}^r = b^*_r,\end{equation*}

where both inequalities coincide with (8) and both equalities with (7). Thus we must have equality all along, and in particular $b_r = b_{1/r}^r$ .

If $b_r$ or $b_{1/r}$ is equal to $0$ , then the same argument shows that both $b_r$ and $b_{1/r}$ are equal to $0$ . This completes the proof.

We now prove Theorem 5.2.

Proof of Theorem 5.2. Assume first that both $b_r$ and $b_{1/r}$ are not $0$ . Choose $P\in I_{n,r,\epsilon }$ such that $|B(P)| = o(|P|)=o(n)$ . Consider a cycle $C$ as in the proof of Theorem 5.1 and connect $\partial P$ to $C$ with a path $\Pi$ of minimal length. Notice that $(\partial ^E P)^*$ is a cycle, hence every $(\partial P \setminus E(\Pi ))^*$ is a connected graph.

Let $X$ be the connected component of $(\partial P \setminus E(\Pi ))^*$ in $G^*$ that is surrounded by $P\cup \Pi \cup C$ , and let $Q$ be the interface of $X$ . Arguing as in the proof of Theorem 5.1, we see that $P^*$ lies in $\partial Q$ , $Q$ has size roughly $n$ , and $(r-\epsilon ^{\prime})|Q|\leq |\partial Q|\leq (r+\epsilon ^{\prime})|Q|$ for some $\epsilon ^{\prime}=\epsilon +o(1)$ .

Let $b^\bullet _r(G)$ be defined like $b_r(G)$ except that we now consider inner interfaces. Thus we have

(9) \begin{equation} b^*_r(G)= b^\bullet _r(G^*) \end{equation}

by the definitions. The above construction now yields the inequality $b^\bullet _r(G) \geq b_r(G)$ .

Combining this with (7), which we rewrite using (9), we obtain

\begin{equation*}b^\bullet _r(G) \geq b_r(G) = \big(b_{1/r}^\bullet (G^*)\big)^r \geq b_{1/r}^\bullet (G^*)^r = b^\bullet _r(G),\end{equation*}

as above, and again equality holds all along. In particular,

$$b_r(G) = b_{1/r}^\bullet (G^*)^r = (b_{1/r}^*(G))^r.$$

If $b_r$ or $b_{1/r}$ is equal to $0$ , then the same argument shows that both $b_r$ and $b_{1/r}$ are equal to $0$ . This completes the proof.

The arguments in the proofs of Proposition 5.3 and Theorem 5.6 can be used to prove Lemma 4.2.

Proof of Lemma 4.2. The inequality $b_r^\circ \leq b_r^\odot$ is obvious.

For the reverse inequality, we will focus on the case of site interfaces. We will construct an array of a certain number of boxes of possibly different sizes, then place the component site interfaces of an arbitrary site multi-interface inside the boxes, and connect them with short paths to obtain a new site interface.

We claim that the number of choices for the shapes of the components of any site multi-interface of size $n$ grows subexponentially in $n$ . Indeed, the number of choices for the shape of any site interface grows polynomially in its size. Theorem 2.1 shows that there are most $s^{\sqrt{n}}$ choices for the component sizes of any site multi-interface of size $n$ , where $s\gt 0$ is a constant. Hence it suffices to show that a site multi-interface of size $n$ comprises $O(\sqrt{n})$ site interfaces.

Let $X=(\ldots,x_{-1},x_0=o,x_1,\ldots )$ be a quasi-geodesic in $G$ containing $o$ and let $X^+=(x_0,x_1,\ldots )$ be the one of the two $1$ -way infinite subpaths of $X$ starting from $o$ . Consider a site multi-interface $P$ of size $n$ . As remarked in the proof of Proposition 4.4, $P$ contains at least one of the first $ln+1$ vertices of $X^+$ . We enumerate the component site interfaces $P_1,P_2,\ldots,P_k$ of $P$ according to the first vertex of $X^+$ that they contain. As the $P_i$ ’s are disjoint, we have $l_i\lt l_{i+1}$ , where $l_i$ is the index of the first vertex of $X^+$ that $P_i$ contains. Since $l_1\geq 0$ , we deduce that $l_i\geq i-1$ for every $i$ . Hence, we obtain

\begin{equation*}|P_i|\geq (i-1)/l\end{equation*}

for every $i=1,2,\ldots,k$ , which implies that

\begin{equation*}n=\sum _{i=1}^k |P_i|\geq \sum _{i=1}^k (i-1)/l=\frac {k(k-1)}{2l}.\end{equation*}

The latter implies that $k=O(\sqrt{n})$ , hence there are $(sn)^{O(\sqrt{n})}$ choices for the shapes of the components site interfaces of any site multi-interface of size $n$ .

We can now restrict to a subfamily $K\subset MI_{n,r,\epsilon }$ of size at least

\begin{equation*}N\,:\!=\dfrac {c_{n,r,\epsilon }}{(sn)^{O(\sqrt {n})}}\end{equation*}

such that all site multi-interfaces of $K$ have the same component sizes, say $\{n_1,n_2,\ldots,n_k\}$ , and corresponding component site interfaces have the same shape. Let $B_1,B_2,\ldots,B_k$ be the boxes of the component site interfaces. Instead of a grid, we construct an array by placing the above $k$ boxes next to each other. Given an element of $K$ , we place its component site interfaces in their boxes. After moving the boxes, if necessary, we connect them with short paths, as described in the proof of Lemma 5.6. Arguing as in the proof of Lemma 5.6 we obtain $b_r^\circ \geq b_r^\odot$ , as desired.

Since ${\mathbb{P}}_{p_c}(|S_o|=n)$ does not decay exponentially in $n$ , we conclude

Corollary 5.7. Consider site percolation on a graph $G\in \mathcal{S}$ satisfying (4). Then, ${\mathbb{P}}_{1-p_c}(|S_o|=n)$ does not decay exponentially in $n$ .

Proof. Notice that $r(1-p_c)=1/r(p_c)$ . The fact that ${\mathbb{P}}_{p_c}(|S_o|=n)$ does not decay exponentially in $n$ implies that $b_{r(p_c)}=f(r(p_c))$ . Theorem 5.1 shows that

\begin{equation*}b_{r(1-p_c)}=b_{r(p_c)}^{1/r(p_c)}=f(r(p_c))^{1/r(p_c)}=f(r(1-p_c)).\end{equation*}

Using Theorem 1.2 we conclude that ${\mathbb{P}}_{1-p_c}(|S_o|=n)$ does not decay exponentially in $n$ .

6. Continuity

In this section, we study the analytical properties of $b_r$ . To avoid repeating the arguments in the proof of Lemma 5.6 and considering cases according to whether we study interfaces or site interfaces, we will prove the results for interfaces in ${\mathbb{Z}}^d$ and $\mathbb{T}^d$ , where the latter graph is defined in (c).

We first prove that the $\limsup$ in the definition of $b_r$ can be replaced by $\lim$ .

Proposition 6.1. Let $G\in \mathcal{S}$ . Then, for every $r$ such that $b_r\gt 1$ and for all but countably many $\epsilon \gt 0$ the limit $\lim _{n\to \infty } c_{n,r,\epsilon }(G)^{1/n}$ exists.

Proof. We will first show that

\begin{equation*}\limsup _{n\to \infty } c_{n,r,\epsilon }^{1/n} = \liminf _{n\to \infty } c_{n,r,\epsilon }^{1/n}\end{equation*}

holds for any $\epsilon \gt 0$ at which the function $\liminf _{n\to \infty } c_{n,r,\epsilon }^{1/n}$ is continuous. Since $\liminf _{n\to \infty } c_{n,r,\epsilon }^{1/n}$ is an increasing function of $\epsilon$ , its points of discontinuity are countably many [41].

Let $\epsilon$ be a point of continuity of $\liminf _{n\to \infty } c_{n,r,\epsilon }^{1/n}$ and $n\in{\mathbb N}$ . By combining elements of $I_{n,r,\epsilon }$ we will construct interfaces of arbitrarily large size and surface-to-volume ratio between $r-\epsilon ^{\prime}$ and $r+\epsilon ^{\prime}$ for some $\epsilon \leq \epsilon ^{\prime}=\epsilon +o(1)$ . Let $0\leq s\leq n+3$ be an integer. We repeat the idea of Proposition 5.3, but instead of a grid, we construct an array of $m$ boxes for some $m\gt 0$ . We place inside each box an element of $I_{n,r,\epsilon }$ and after moving the boxes, if necessary, we connect consecutive interfaces using paths of length $4$ , similarly to the proof of Proposition 5.3. We also attach a path of length $s+4$ , that is incident to the last interface and disjoint from any of the previous interfaces. In this way, we produce an element $Q$ of $I_{k,r,\epsilon ^{\prime}}$ , where $\epsilon ^{\prime}=\epsilon +o(1)$ and $k$ is any integer of the form $k=m(n+4)+s$ . There are roughly $c_{n,r,\epsilon }^m$ choices for $Q$ . Since $s$ ranges between $0$ and $n+3$ , for every fixed $n$ , all but finitely many $k$ can be written in this form for some $m\geq 1$ . Taking the $k$ th root and then the limit as $m\to \infty$ we conclude that $\liminf _{k\to \infty } c_{k,r,\epsilon ^{\prime}}^{1/k}\geq c_{n,r,\epsilon }^{1/(n+4)}$ . Letting $n\to \infty$ we obtain $\liminf _{n\to \infty } c_{n,r,\epsilon }^{1/n} \geq \limsup _{n\to \infty } c_{n,r,\epsilon }^{1/n}$ . The above inequality follows from the fact that $\epsilon$ is a point of continuity of $\liminf _{n\to \infty } c_{n,r,\epsilon }^{1/n}$ . Hence $\liminf _{n\to \infty } c_{n,r,\epsilon }^{1/n} = \limsup _{n\to \infty } c_{n,r,\epsilon }^{1/n}$ , as desired

The following proposition follows directly from the definition of $b_r$ :

Proposition 6.2. Let $G\in \mathcal{S}$ . Then $b_r(G)$ is an upper-semicontinuous function of $r$ .

Proof. Let $\epsilon \gt 0$ and $0\lt \delta \lt \epsilon/2$ . Then for every $r\gt 0$ and for every $s$ with $|r-s|\lt \epsilon/2$ , the interval $(s-\delta,s+\delta )$ is contained in $(r-\epsilon,r+\epsilon )$ , and the site interfaces $P$ with $|\partial P|/|P| \in (s-\delta,s+\delta )$ are counted in the set of those site interfaces with $|\partial P|/|P| \in (r-\epsilon,r+\epsilon )$ as well. Hence, $\limsup _{n\to \infty } c_{n,r,\epsilon }^{1/n}\geq \limsup _{n\to \infty } c_{n,s,\delta }^{1/n}$ . Taking limits as $\delta \to 0$ , $s\to r$ and finally $\epsilon \to 0$ , we obtain $b_r \geq \limsup _{s\to r} b_s$ . The latter shows that $b_r$ is an upper-semicontinuous function of $r$ .

Next, we prove that $b_r$ is a log-concave function of $r$ .

Proposition 6.3. Let $G\in \mathcal{S}$ . Then for any $t\in (0,1)$ and any $r,s$ such that $b_r(G),b_s(G)\gt 1$ , we have $b_{tr+(1-t)s}(G) \geq b_r(G)^{t} b_s(G)^{1-t}$ .

Proof. Pick an $\epsilon \gt 0$ such that both $\lim _{n\to \infty } c_{n,r,\epsilon }^{1/n}$ and $\lim _{n\to \infty } c_{n,s,\epsilon }^{1/n}$ exist. Let $(p_m/q_m)$ be a sequence of rational numbers converging to $t$ such that $p_m\to \infty$ and $q_m\to \infty$ . Our aim is to construct an interface $(Q,\partial Q)$ with $Q$ of size roughly $q_m$ and $\partial Q$ of size roughly $rp_m+s(q_m-p_m)$ , in which case the surface-to-volume ratio is roughly $tr+(1-t)s$ .

To this end, consider $m$ large enough so that $q_m\gt p_m$ . Note that there exist subfamilies $K$ , $K^{\prime}$ of $I_{p_m,r,\epsilon }$ and $I_{q_m-p_m,s,\epsilon }$ and a polynomial $P(x)$ such that the elements of both $K$ and $K^{\prime}$ have the same shape (as defined in the proof of Proposition 5.3), and $|K|\geq c_{p_m,r,\epsilon }/P(p_m)$ , $|K^{\prime}|\geq c_{q_m-p_m,s,\epsilon }/P(q_m-p_m)$ . Note that the elements of $K$ and $K^{\prime}$ share the same boxes $B$ and $B^{\prime}$ , respectively. Consider an interface chosen from $K$ and another interface chosen from $K^{\prime}$ , and place them in an array of two boxes $B_1$ and $B_2$ , where $B_1$ has the same dimensions as $B$ and $B_2$ has the same dimensions as $B^{\prime}$ . Moving $B_1$ and $B_2$ as appropriate, we can connect the interfaces with paths of length $O(1)$ .

In this way, we obtain an interface $Q$ of size $k=q_m+O(1)$ and surface-to-volume ratio

\begin{equation*}\frac {p_m}{q_m}(r-\varepsilon )+\bigg(1-\frac {p_m}{q_m}\bigg)(s-\varepsilon )-o(1)\leq \frac {|\partial Q|}{|Q|}\leq \frac {p_m}{q_m}(r+\varepsilon )+\bigg(1-\frac {p_m}{q_m}\bigg)(s+\varepsilon )+o(1),\end{equation*}

which converges to $tr+(1-t)s$ as $m$ tends to infinity and $\varepsilon$ to $0$ . Notice that we have at least

\begin{equation*}\frac {c_{p_m,r,\epsilon } c_{q_m-p_m,s,\epsilon }}{P(p_m) P(q_m-p_m)}\end{equation*}

choices for $Q$ . Taking the $k$ th root of the latter expression and letting $m\to \infty$ gives

\begin{equation*}\lim _{n\to \infty } c_{n,r,\epsilon }^{t/n} \lim _{n\to \infty } c_{n,s,\epsilon }^{(1-t)/n}.\end{equation*}

Letting $\epsilon \to 0$ along a sequence of points such that both $\lim _{n\to \infty } c_{n,r,\epsilon }^{1/n}$ and $\lim _{n\to \infty } c_{n,s,\epsilon }^{1/n}$ exist, we obtain $b_{tr+(1-t)s} \geq b_r^t b_s^{1-t}$ as desired.

We expect Proposition 6.3, and as a result Theorem 6.4 below, to hold in much greater generality than $G\in \mathcal{S}$ , namely for all 1-ended Cayley graph s. In order to be able to put several interfaces close to each other to connect them with short paths as in the above proof, it could be handy to use [3, Lemma 6].

Let $I$ be the closure of the set of $r$ such that $b_r\gt 1$ . Proposition 6.3, combined with Proposition 6.2, easily implies the following.

Theorem 6.4. Let $G\in \mathcal{S}$ . Then $b_r(G)$ is a continuous function of $r$ on $I$ .

Proof. By Proposition 6.3, $I$ is an interval, and the only possible $r\in I$ such that $b_r=1$ , are its endpoints. For every $r$ in $I$ , we have $\limsup _{s \to r} b_s \leq b_r$ by Proposition 6.2. Using Proposition 6.3 for $t=1/2$ we obtain $\liminf _{s\to r} b_{(r+s)/2} \geq \sqrt{b_r \liminf _{s \to r} b_s}$ for every $r$ such that $b_r\gt 1$ . This immediately implies that $\liminf _{s\to r} b_s\geq b_r$ and thus $\lim _{s\to r} b_s = b_r$ .

On the other hand, if $b_r=1$ for some of the endpoints of $I$ , then Proposition 6.2 and the fact that $b_s\gt 1$ for $s$ in the interior of $I$ , give that

\begin{equation*}\mathop {\lim _{s\to r}}_{s\in I} b_s= 1.\end{equation*}

Therefore, $b_r$ is a continuous function on $I$ .

Having proved that $b_r$ is a continuous function, the next natural question is whether it is differentiable. It turns out that this holds everywhere except, perhaps, on a countable set.

Corollary 6.5. Let $G\in \mathcal{S}$ . Then $b_r(G)$ is differentiable for all but countably many $r$ .

Proof. By Proposition 6.3, $\log b_r$ is a concave function, hence differentiable everywhere except for a countable set [40]. It follows immediately that this holds for $b_r$ as well.

7. Bounds on growth rates of lattice animals and interfaces

In this section, we exploit the machinery developed above in order to obtain bounds on the exponential growth rates of lattice (site) animals in ${\mathbb{Z}}^d$ .

A lattice animal in a graph $G$ is a connected subgraph of $G$ containing $o$ . A lattice tree in $G$ is a lattice animal that is also a tree. Let $a_n(G)$ be the number of all lattice animals of $G$ with $n$ edges, and let $t_n(G)$ be the number of all lattice trees of $G$ with $n$ edges. It is well known that both $a({\mathbb{Z}}^d)\,:\!=\lim _{n\to \infty }{a_n({\mathbb{Z}}^d)}^{1/n}$ and $t({\mathbb{Z}}^d)\,:\!=\lim _{n\to \infty }{t_n({\mathbb{Z}}^d)}^{1/n}$ exist [30, 32].

A lattice site animal in $G$ is a set of vertices of $G$ containing $o$ that spans a connected graph. A lattice site tree in $G$ is a lattice site animal in $G$ that spans a tree. Let $\dot{a}_n(G)$ be the number of all lattice site animals of $G$ with $n$ vertices, and let $\dot{t}_n(G)$ be the number of all lattice trees of $G$ with $n$ vertices. We let $\dot{a}(G)\,:\!=\lim _{n\to \infty }{\dot{a}_n(G)}^{1/n}$ and $\dot{t}(G)\,:\!=\lim _{n\to \infty }{\dot{t}_n(G)}^{1/n}$ whenever the limits exist. It is well known that both limits exist in the case of ${\mathbb{Z}}^d$ .

Our results allow us to translate any upper bound on $\dot{p}_c(G)$ into a lower bound on $\dot{a}(G)$ , and conversely any upper bound on $\dot{a}(G)$ into a lower bound on $\dot{p}_c(G)$ . Indeed, we just remark that

(10) \begin{equation} \dot{a}(G) \geq \dot{b}(G) \geq \dot{b}_r(\dot{p}_c(G)) = f(r(\dot{p}_c(G))) \end{equation}

for every lattice $G$ , where the two inequalities are obvious from the definitions (interfaces are a species of lattice animal), and the last equality is given by Theorem 4.8. To translate bounds on $\dot{p}_c(G)$ into bounds on $\dot{a}(G)$ and vice versa, we just remark that $f(r)$ is monotone increasing in $r$ and $r(p)$ is monotone decreasing in $p$ . Inequality (10) and the above reasoning applies verbatim to $p_c(G)$ and ${a}(G)$ .

Recently, Barequet and Shalah [6] proved that $\dot{a}({\mathbb{Z}}^3)\lt 9.3835$ . Plugging this into (10), we deduce

(11) \begin{equation} \dot{p}_c({\mathbb{Z}}^3)\gt r^{-1} \circ f^{-1}(9.3835) \gt 0.2522. \end{equation}

Theorem 7.1. We have $\dot{p}_c({\mathbb{Z}}^3)\gt 0.2522$ .

As far as we know, the best rigorous bound previously known was about $\dot{p}_c({\mathbb{Z}}^3)\gt 0.21225$ , obtained as the inverse of the best known bound on the connective constant [34]. ²

In two dimensions we cannot hope to get close to the real value of $\dot{a}(G)$ with this technique, as we are only enumerating the subspecies of site interfaces. ³ But as we will see in the next section, our lower bounds become asymptotically tight as the dimension $d$ tends to infinity. In Section 8 we will argue conversely: we will prove upper bounds on $\dot{a}({\mathbb{Z}}^d)$ and plug them into (10) to obtain lower bounds on $\dot{p}_c({\mathbb{Z}}^d)$ .

7.1. Asymptotic expansions

Our first result provides the first terms of the $1/d$ asymptotic expansion of the exponential growth rate of interfaces:

Theorem 7.2. The exponential growth rate of the number of interfaces of ${\mathbb{Z}}^d$ satisfies $b({\mathbb{Z}}^d)=2de-\dfrac{3e}{2}-O(1/d)$ .

Proof. We claim that for any interface $P$ of ${\mathbb{Z}}^d$ we have $|\partial P|\leq (2d-2)|P|+2d$ . Indeed, summing vertex degrees gives $\sum _{u\in V(P)} \text{deg}(u)\geq 2|P|+|\partial P|$ , where $\text{deg}(u)$ is the degree of $u$ in the graph $P\cup \partial P$ , because the edges of $P$ are counted twice, and the edges of $\partial P$ are counted at least once. Since $\text{deg}(u)\leq 2d$ and $|V(P)|\leq |P|+1$ , we get

\begin{equation*}2|P|+|\partial P|\leq \sum _{u\in V(P)} \text {deg}(u)\leq 2d |V(P)|\leq 2d|P|+2d.\end{equation*}

By rearranging we obtain the desired inequality. It follows that $b_r=0$ for every $r\gt 2d-2$ which combined with (6) and the fact that $f(r)$ is an increasing function of $r$ gives

\begin{equation*}b_r({\mathbb {Z}}^d)\leq \dfrac {(2d-1)^{(2d-1)}}{(2d-2)^{(2d-2)}}\end{equation*}

for $r\geq 0$ . Using (4.3) we obtain that

(12) \begin{align} b({\mathbb{Z}}^d)\leq \dfrac{(2d-1)^{(2d-1)}}{(2d-2)^{(2d-2)}}. \end{align}

Notice that for every $r\gt 0$ ,

\begin{equation*}\dfrac {(1+r)^{1+r}}{r^r}=(1+r)\Big (1+\dfrac {1}{r}\Big )^r=(1+r)\exp \Big (r\log \Big (1+\dfrac {1}{r}\Big )\Big ).\end{equation*}

Using the Taylor expansion $\log \Big (1+\dfrac{1}{r}\Big )=\dfrac{1}{r}-\dfrac{1}{2r^2}+\dfrac{1}{3r^3}-O(1/r^4)$ we obtain

\begin{equation*}\dfrac {(1+r)^{1+r}}{r^r}=(1+r)\exp \Big (1-\dfrac {1}{2r}+\dfrac {1}{3r^2}-O(1/r^3)\Big )\end{equation*}

as $r\to \infty$ . Now the Taylor expansion

\begin{equation*}\exp (1+x)=e\Big (1+x+\dfrac {x^2}{2}+O(x^3)\Big )=e\Big (1-\dfrac {1}{2r}+\dfrac {11}{24r^2}-O(1/r^3)\Big ),\end{equation*}

where $x=-\dfrac{1}{2r}+\dfrac{1}{3r^2}-O(1/r^3)$ , gives

\begin{align*} (1+r)\exp \Big (1-\dfrac{1}{2r}+\dfrac{1}{3r^2}-O(1/r^3)\Big )&=(1+r)e\Big (1-\dfrac{1}{2r}+\dfrac{11}{24r^2}-O(1/r^3)\Big )\\ & = er+\dfrac{e}{2}-O(1/r). \end{align*}

Consequently,

(13) \begin{align} \dfrac{(1+r)^{1+r}}{r^r}=er+\dfrac{e}{2}-O(1/r). \end{align}

Plugging $r=2d-2$ in (13) we deduce that

(14) \begin{align} \dfrac{(2d-1)^{(2d-1)}}{(2d-2)^{(2d-2)}}=2de-3e/2-O(1/d), \end{align}

which combined with (12) establishes the desired upper bound.

For the lower bound, we have $b({\mathbb{Z}}^d)\geq b_{r_d}({\mathbb{Z}}^d)$ and $b_{r_d}({\mathbb{Z}}^d)=f(r_d)$ , where $r_d\,:\!=r(p_c({\mathbb{Z}}^d))$ . It has been proved in [20, 26] that

(15) \begin{align} p_c({\mathbb{Z}}^d)=\dfrac{1}{2d}+\dfrac{1}{(2d)^2}+\dfrac{7}{2(2d)^3}+O(1/d^4), \end{align}

hence

\begin{equation*}r_d=\frac {1-p_c({\mathbb {Z}}^d)}{p_c({\mathbb {Z}}^d)}=\dfrac {16d^4}{8d^3+4d^2+7d+O(1)}-1.\end{equation*}

We can easily compute that

\begin{align*} \dfrac{16d^4}{8d^3+4d^2+7d+O(1)}&= 2d-\dfrac{8d^3+14d^2+O(d)}{8d^3+4d^2+7d+O(1)}\\ & = 2d-\dfrac{8d^3+4d^2}{8d^3+4d^2+7d+O(1)}-O(1/d) \end{align*}

and

\begin{equation*}\dfrac {8d^3+4d^2}{8d^3+4d^2+7d+O(1)}=\dfrac {1}{1+O(1/d^2)}=1-O(1/d^2).\end{equation*}

Hence $r_d=2d-2-O(1/d)$ , which implies that

\begin{equation*}b_{r_d}({\mathbb {Z}}^d)=\frac {(1+r_d)^{1+r_d}}{r_d^{r_d}}=2de-3e/2-O(1/d).\end{equation*}

Therefore, $b({\mathbb{Z}}^d)=2de-\dfrac{3e}{2}-O(1/d)$ as desired.

We remark that the asymptotic expansions of $\dfrac{(2d-1)^{(2d-1)}}{(2d-2)^{(2d-2)}}$ and $b_{r_d}$ differ in their third terms, and so we are unable to compute the third term in the asymptotic expansion of $b({\mathbb{Z}}^d)$ . It follows from the proof of Theorem 7.2 above that $b({\mathbb{Z}}^d)-b_{r_d}({\mathbb{Z}}^d)=O(1/d)$ , that is $b_{r_d}$ is a good approximation of $b({\mathbb{Z}}^d)$ .

Next, we use Theorem 7.2 and Kesten’s argument [18] to obtain the first two terms in the asymptotic expansion of $a({\mathbb{Z}}^d)$ . These had already been obtained by Miranda and Slade [37] but our proof is shorter.

Theorem 7.3. $a({\mathbb{Z}}^d)=2de-\dfrac{3e}{2}-O(1/d)$ .

Proof. Let $C$ be a connected subgraph containing $o$ and recall the definition of the edge boundary $\partial _E C$ . Arguing as in the proof of Theorem 7.2, we obtain that $|\partial _E C|\leq (2d-2)|E(C)|+2d$ . It follows that for every $p\in (0,1)$ .

\begin{equation*}a_n({\mathbb {Z}}^d)p^n (1-p)^{(2d-2)n+2d} \leq {\mathbb {P}}_p(|E(C_o)|=n)\leq 1.\end{equation*}

Choosing $p=\frac{1}{2d-1}$ and dividing by $p^n (1-p)^{(2d-2)n+2d}$ , we deduce from (14) that

\begin{equation*}a({\mathbb {Z}}^d)\leq \frac {(2d-1)^{(2d-1)}}{(2d-2)^{(2d-2)}}=2de-3e/2-O(1/d).\end{equation*}

Since $a({\mathbb{Z}}^d)\geq b({\mathbb{Z}}^d)$ , the lower bound follows from Theorem 7.2.

The behaviour of $a({\mathbb{Z}}^d)$ , and the analogue $t({\mathbb{Z}}^d)$ for lattice trees, has been extensively studied in the physics literature. Precise asymptotic expansions for $a({\mathbb{Z}}^d)$ and $t({\mathbb{Z}}^d)$ were reported in [15], [22, 38], respectively, but without any rigorous bounds on the error terms. Miranda and Slade [36] proved that both $a({\mathbb{Z}}^d)$ and $t({\mathbb{Z}}^d)$ are asymptotic to $2de$ . The first three terms of $a({\mathbb{Z}}^d)$ and $t({\mathbb{Z}}^d)$ have been computed rigorously by the same authors in [37].

7.2. Site variants

We now prove analogous results for site interfaces and site animals. We start with a weaker analogue of Theorem 7.2:

Theorem 7.4. The exponential growth rate of the number of site interfaces of ${\mathbb{Z}}^d$ satisfies $\dot{b}({\mathbb{Z}}^d)=2de-O(1)$ .

Proof. Similarly to the proof of Theorem 7.2, we will show that for any site interface $P$ of ${\mathbb{Z}}^d$ we have $|\partial P|\leq (2d-2)|P|+2$ . Let $k$ be the number of edges of the graph spanned by $P$ , and let $l$ be the number of edges with one end vertex in $P$ and one in $\partial P$ . Notice that $k\geq |P|-1$ and $l\geq |\partial P|$ . Arguing as in the proof of Theorem 7.2 we obtain

\begin{equation*}2(|P|-1)+|\partial P|\leq 2k+l\leq 2d|P|.\end{equation*}

By rearranging we obtain the desired inequality. Arguing as in the proof of Theorem 7.2 we obtain

\begin{equation*}\dot {b}({\mathbb {Z}}^d)\leq \frac {(2d-1)^{(2d-1)}}{(2d-2)^{(2d-2)}}=2de-O(1).\end{equation*}

Moreover, we have that $\dot{b}({\mathbb{Z}}^d)\geq \dot{b}_{\dot{r}_d}({\mathbb{Z}}^d)$ and $\dot{b}_{\dot{r}_d}({\mathbb{Z}}^d)=f(\dot{r}_d)$ , where $\dot{r}_d\,:\!=r({\dot{p}_c}({\mathbb{Z}}^d))$ . Hara and Slade [20] proved that ${\dot{p}_c}({\mathbb{Z}}^d)=\big (1+O(1/d)\big )/2d$ , hence

\begin{equation*}\dot {r}_d=\frac {1-{\dot {p}_c}({\mathbb {Z}}^d)}{{\dot {p}_c}({\mathbb {Z}}^d)}=\dfrac {2d}{1+O(1/d)}-1.\end{equation*}

Using (13) we obtain

\begin{equation*}\dot {b}_{\dot {r}_d}({\mathbb {Z}}^d)=\frac {(1+\dot {r}_d)^{1+\dot {r}_d}}{\dot {r}_d^{\dot {r}_d}}=\dfrac {2de}{1+O(1/d)}-e/2-O(1/d).\end{equation*}

Since $\dfrac{1}{1+O(1/d)}=1-O(1/d)$ , we have

\begin{equation*}\dfrac {2de}{1+O(1/d)}-e/2-O(1/d)=2de\Big (1-O(1/d)\Big )-e/2-O(1/d)=2de-O(1).\end{equation*}

Therefore, $\dot{b}_{\dot{r}_d}({\mathbb{Z}}^d)=2de-O(1)$ , which implies that $\dot{b}({\mathbb{Z}}^d)=2de-O(1)$ as desired.

In the previous section we used (10) and (15) to lower bound $b({\mathbb{Z}}^d)$ . Recently, Heydenreich and Matzke [25] proved that ⁴

(17) \begin{align} {\dot{p}_c}({\mathbb{Z}}^d)=\dfrac{1}{2d}+\dfrac{5}{2(2d)^2}+\dfrac{31}{4(2d)^3}+O(1/d^4). \end{align}

Combining (17) with our above method gives the lower bound $\dot{a}({\mathbb{Z}}^d)\geq \dot{b}({\mathbb{Z}}^d)\geq 2de-3e+O(1/d)$ . Arguing as in Theorem 7.3, we can easily obtain

Theorem 7.5. $\dot{a}({\mathbb{Z}}^d)\leq 2de-O(1)$ and $\dot{a}({\mathbb{Z}}^d)\geq 2de-3e+O(1/d)$ .

Barequet, Barequet and Rote [4] proved the weaker result $\dot{a}({\mathbb{Z}}^d)=2de-o(d)$ , and they conjectured that $\dot{a}({\mathbb{Z}}^d)=2de-3e+O(1/d)$ in agreement with physicists’ predictions [38, (2.22)], so it only remains to prove a matching upper bound. ⁵ We will improve the upper bound in Theorem 8.1 below. We remark that under the assumption $\dot{a}({\mathbb{Z}}^d)=2de-3e+O(1/d)$ holds, we obtain $\dot{b}({\mathbb{Z}}^d)-\dot{b}_{\dot{r}_d}({\mathbb{Z}}^d)=O(1/d)$ .

8. Upper bounds for lattice site animals

In the previous section, we used Kesten’s argument in order to bound $\dot{a}({\mathbb{Z}}^d)$ from above. Another method that gives the same upper bounds for $\dot{a}({\mathbb{Z}}^d)$ was introduced by Eden [13]. Eden described a procedure that associates in a canonical way, a spanning tree and a binary sequence to every lattice site animal. This reduces the problem of counting lattice site animals to a problem of counting binary sequences with certain properties. Klarner and Rivest [31] enhanced Eden’s method in the case of ${\mathbb{Z}}^2$ , proving that $\dot{a}({\mathbb{Z}}^2)\leq 4.6496$ . Recently, Barequet and Shalah [6] extended this enhancement to higher dimensions, obtaining $\dot{a}({\mathbb{Z}}^d)\leq 2de-2e+1/(2d-2)$ .

In this section we will utilise Eden’s procedure to reduce the gap between the aforementioned inequality and the conjectured asymptotic expansion $\dot{a}({\mathbb{Z}}^d)=2de-3e+O(1/d)$ mentioned in the previous section:

Theorem 8.1. We have $\dot{a}({\mathbb{Z}}^d)\leq 2de-5e/2+O(1/\log (d))$ .

Our result improves the bounds of Barequet and Shalah [6] for every large enough $d$ .

We remark that $\dot{b}_{r_d}({\mathbb{Z}}^d)=2de-3e+O(1/d)$ by (17). It is reasonable to expect that both $\dot{b}({\mathbb{Z}}^d)-\dot{b}_{r_d}({\mathbb{Z}}^d)=O(1/d)$ and $\dot{a}({\mathbb{Z}}^d) - \dot{b}({\mathbb{Z}}^d)=O(1/d)$ hold, as it happens for the bond variants, which would imply the aforementioned conjecture $\dot{a}({\mathbb{Z}}^d)=2de-3e+O(1/d)$ .

In order to prove Theorem 8.1, we will show that a typical lattice site animal has volume-to-surface ratio that is bounded away from its maximal possible value, namely $2d-2$ .

We will need the following definition. We let $\dot{a}_{n,r,\epsilon }$ denote the number of lattice site animals $X$ of ${\mathbb{Z}}^d$ containing $o$ with $|X|=n$ and $(r-\epsilon )n \leq |\partial _V X| \leq (r+\epsilon )n$ , and we define

\begin{equation*}\dot {a}_r=\dot {a}_r({\mathbb {Z}}^d)\,:\!= \lim _{\epsilon \to 0} \limsup _{n\to \infty } {\dot {a}_{n,r,\epsilon }({\mathbb {Z}}^d)}^{1/n}.\end{equation*}

Using Kesten’s argument, one can show that

(18) \begin{equation} \dot{a}_r \leq f(r). \end{equation}

for every $r\gt 0$ . This follows from the work of Hammond [19], and it can also be seen as a special case of (6), since by choosing the full cycle space of ${\mathbb{Z}}^d$ as its basis, each lattice site animal $P$ is a site interface with $\partial P=\partial _V P$ .

For the proof of Theorem 8.1 we will need a result which bounds $\dot{a}_r({\mathbb{Z}}^d)$ for $r$ close to $2d-2$ . We remark that $\dot{a}_{2d-2}({\mathbb{Z}}^d)\geq \dot{b}_{2d-2}({\mathbb{Z}}^d)\geq 1$ , as a straight path has volume-to-surface ratio roughly $2d-2$ .

Before proving this result, let us first introduce some necessary definitions which will allow us to describe Eden’s procedure. The lexicographical ordering of ${\mathbb{Z}}^d$ is defined as follows. We say that a vertex $u=(u_1,u_2,\ldots,u_d)$ is smaller than a vertex $v=(v_1,v_2,\ldots,v_d)$ if there is some $i=1,2,\ldots,d$ such that $u_i\leq v_i$ and $u_j=v_j$ for every $j\lt i$ . We also order the directed edges of the form $\vec{ou}$ in an arbitrary way. The latter ordering induces by translation a natural ordering of the set of directed edges with a common initial end vertex $v$ , where $v$ is any vertex of ${\mathbb{Z}}^d$ .

We will now describe Eden’s procedure. Let $X$ be a lattice site animal of size $n$ in ${\mathbb{Z}}^d$ containing $o$ . We will assign to $X$ a unique binary sequence $S=S(X)=(s_1,s_2,\ldots,s_{(2d-1)n-d+1})$ of length $(2d-1)n-d+1$ . To this end, we will reveal the vertices of $X$ one by one in a specific way. Let $v_1$ be the lexicographically smallest vertex of $X$ , and notice that $v_1$ has at most $d$ neighbours in $X$ . For every $i=1,\ldots,d$ , we let $s_i$ take the value $1$ if the $i$ th directed edge of the form $\vec{u_1v}$ in the above ordering lies in the set of directed edges $\overleftrightarrow{E(X)}$ of $X$ , and $0$ otherwise. The ordering of these directed edges induces an ordering on the neighbours of $u_1$ in $P$ . We reveal the neighbours of $u_1$ in $X$ one by one according to the latter ordering, and we let $u_{j+1}$ be the $j$ th revealed vertex. Now we proceed to the lexicographically smaller neighbour of $u_1$ lying in $X$ , denoted $w$ . The valid directed edges starting from $w$ are those not ending at $u_1$ , and there are exactly $2d-1$ of them. The ordering of the whole set of directed edges starting from $w$ induces an ordering of the set of valid directed edges starting from $w$ . For every $i=d+1,\ldots,3d-1$ , we let $s_i$ take the value $1$ if the $(i-d)$ th valid directed edge of the form $\vec{wv}$ lies in $\overleftrightarrow{E(X)}$ and $v$ has not been revealed so far (the latter is always true in this step but not necessarily in the following steps), and $0$ otherwise. We reveal the corresponding neighbours of $w$ in $X$ one by one, and we label them $u_k,u_{k+1}\ldots,$ where $k$ is the smallest index not previously used. Now we proceed as before up to the point that all vertices of $X$ have been revealed, and we set to $0$ all the remaining entries of $S$ that have not already been set to some value. Notice that $S$ contains exactly $n-1$ $1$ ’s, since $P$ has size $n$ .

We will now prove the following result.

Lemma 8.2. Consider some $0\leq x \leq 1$ , and let $y=\min \{x,1/2\}$ . Then

\begin{equation*}\dot {a}_{2d-2-x}({\mathbb {Z}}^d) \leq \dfrac {(2d-1)^{2d-1}}{y^y (1-y)^{1-y} x^x (2d-1-x)^{2d-1-x}}.\end{equation*}

In particular, $\dot{a}_{2d-2}({\mathbb{Z}}^d)=1$ .

Proof. For $x=1$ we have $y=1/2$ , and so the claimed upper bound is equal to

\begin{equation*}2\dfrac {(2d-1)^{2d-1}}{(2d-2)^{2d-2}},\end{equation*}

which is in turn equal to $2f(2d-2)$ . Since $f(r)$ is an increasing function,

\begin{equation*}f(2d-3)\leq f(2d-2)\leq 2f(2d-2).\end{equation*}

The assertion now follows in the case $x=1$ from the fact that $\dot{a}_{2d-3}({\mathbb{Z}}^d)\leq f(2d-3)$ . So let us assume that $x\lt 1$ .

Consider some numbers $n\in \mathbb{N}$ , and $\epsilon \gt 0$ with $x+\epsilon \lt 1$ . Let $X$ be a lattice site animal of size $n$ in ${\mathbb{Z}}^d$ containing $o$ such that $(2d-2-x-\epsilon )n\leq |\partial _V X|\leq (2d-2-x+\epsilon )n$ . Recall Eden’s procedure and the notation introduced there. This procedure defines naturally a spanning subtree $T$ of $X$ rooted at $u_1$ , by attaching an edge $u_k u_l$ , $k\lt l$ to $T$ when $u_l$ is one of the neighbours of $u_k$ revealed when considering the valid directed edges starting from $u_k$ . Given an edge $uv$ of $T$ with $u$ being the ancestor of $v$ , we say that $uv$ is a turn of $T$ if $uv$ is perpendicular to the edge $zu$ of $T$ , where $z$ is the (unique) ancestor of $u$ . We denote by $t$ the number of turns of $T$ .

Claim 1. We claim that

(19) \begin{align} |\partial _V X|\leq (2d-2)n-t+2. \end{align}

Indeed, for every $k=1,2,\ldots,n$ , let $T_k$ be the subtree of $T$ with $V(T_k)=\{u_1,u_2,\ldots,u_k\}$ . Let $\partial T_k$ be the set of vertices in ${\mathbb{Z}}^d\setminus \{u_1,u_2,\ldots,u_k\}$ having a neighbour in $\{u_1,u_2,\ldots,u_k\}$ . Write $t_k$ for the number of turns of $T_k$ . We will prove inductively that

\begin{equation*}|\partial T_k|\leq (2d-2)|T_k|-t_k+2\end{equation*}

for every $k=1,2,\ldots,n$ . The claim will then follow once we observe that $|\partial _V X|= |\partial T_n|$ , $|X|=|T_n|=n$ and $t=t_n$ . For $k=1$ , the assertion clearly holds. Assume that it holds for some $1\leq k\lt n$ . Notice that we always have $|T_{k+1}|=|T_k|+1$ and $|\partial T_{k+1}|\leq |\partial T_k|+2d-2$ , because $u_{k+1}$ lies in $\partial T_k$ and at most $2d-1$ neighbours of $u_{k+1}$ lie in $\partial T_{k+1}$ . If $t_{k+1}=t_k$ , then we get $|\partial T_{k+1}|\leq (2d-2)|T_{k+1}|-t_{k+1}+2$ , as claimed. Suppose that $t_{k+1}=t_k +1$ . Consider the ancestor $u_l$ of $u_{k+1}$ , and the ancestor $u_m$ of $u_l$ . Since by adding $u_{k+1}$ to $T_k$ we create one more turn, $u_{k+1}$ , $u_l$ and $u_m$ are three vertices of a common square. Let $w$ be the fourth vertex. Notice that $w$ lies in $T_k \cup \partial T_k$ . Thus, at most $2d-2$ neighbours of $u_{k+1}$ lie in $\partial T_{k+1} \setminus \partial T_k$ . Therefore, $|\partial T_{k+1}|\leq (2d-2)|T_{k+1}|-t_{k+1}+2$ , as desired. This completes the proof of (19).

We will now utilise (19) to prove the statement of the lemma. Our assumption $(2d-2-x-\epsilon )n\leq |\partial _V X|$ combined with (19) implies that $t\leq (x+\epsilon )n+2$ . Hence it suffices to find an upper bound for the number of lattice site animals $Q$ of size $n$ with $t\leq q\,:\!=(x+\epsilon )n+2$ .

Claim 2. We claim that the number $\dot{a}_n$ of such lattice site animals of size $n$ satisfies

(20) \begin{align} \dot{a}_n\leq \sum _{i=1}^d \sum _{j=0}^{\min \{q,n-i\}}\begin{pmatrix}d \\ i\end{pmatrix}\begin{pmatrix}(2d-1)(n-1) \\ j\end{pmatrix}\begin{pmatrix}n-1 \\ n-i-j\end{pmatrix}. \end{align}

Indeed, let $i$ be number of neighbours of $u_1$ in $Q$ , let $j$ be the number of $1$ ’s contributing to the number of turns in those bits of $S(Q)$ . Let us apply the following steps in turn:

1. (i) Set $i$ entries of $(s_1,\ldots,s_d)$ equal to $1$ ,

2. (ii) Choose which entries of $S(Q)$ contribute to the number of turns,

3. (iii) Choose which bits, except for the first one, contain an additional $1$ .

After the first two steps, we have specified which entries of $S(Q)$ are set to $1$ , except for those that do not contribute to the number of turns. Since for every vertex of $Q$ , at most one of its children does not contribute to the number of turns, we conclude that at most one entry of each of the bits chosen in the fourth step can be set to $1$ , the position of which in $S(Q)$ is uniquely determined by the values of the remaining entries of $S(Q)$ . It is easy to see now that for every $i$ and $j$ , there are at most

\begin{equation*}\begin{pmatrix}d \\ i\end{pmatrix}\begin{pmatrix}(2d-1)(n-1) \\ j\end{pmatrix} \begin{pmatrix}n-1 \\ n-i-j\end{pmatrix}\end{equation*}

possibilities for $Q$ , and so (20) can be obtained by summing over all possible values of $i$ and $j$ .

We will now handle the sum in the right-hand side of (20). Since the binomial coefficient $(\begin{smallmatrix}m \\ l\end{smallmatrix})$ is an increasing function of $l$ when $l\leq m/2$ , we have

\begin{equation*}\begin{pmatrix}(2d-1)(n-1) \\ j\end{pmatrix}\leq \begin{pmatrix}(2d-1)(n-1) \\ q\end{pmatrix}.\end{equation*}

Using Stirling’s approximation $m!=\big (1+o(1)\big ) \sqrt{2\pi m}(m/e)^m$ we obtain

\begin{equation*}\begin{pmatrix}(2d-1)(n-1) \\ q\end{pmatrix}\approx \dfrac {(2d-1)^{(2d-1)n}}{(x+\epsilon )^{x+\epsilon }(2d-1-x-\epsilon )^{(2d-1-x-\epsilon )n}},\end{equation*}

where $\approx$ denotes equality up to a multiplicative constant that is $O(c^n)$ for every $c\gt 1$ . Clearly

\begin{equation*}\begin{pmatrix}n-1 \\ n-i-j\end{pmatrix}\leq 2^n.\end{equation*}

It follows that

\begin{equation*}\dot {a}_{n,2d-2-x,\epsilon } \lesssim 2^n \dfrac {(2d-1)^{(2d-1)n}}{(x+\epsilon )^{x+\epsilon }(2d-1-x-\epsilon )^{(2d-1-x-\epsilon )n}},\end{equation*}

where $\lesssim$ denotes inequality up to a multiplicative constant that is $O(c^n)$ for every $c\gt 1$ . Taking $n$ th roots and letting $n\to \infty$ and $\epsilon \to 0$ we obtain

\begin{equation*}\dot {a}_{2d-2-x}\leq 2 \dfrac {(2d-1)^{2d-1}}{x^x(2d-1-x)^{2d-1-x}}.\end{equation*}

The above bound can be improved when $x\lt 1/2$ . Suppose that $x\lt 1/2$ . We can choose $\epsilon \gt 0$ small enough, and increase the value of $n$ , if necessary, to ensure that $q+d\lt n/2$ . Since the binomial coefficient $(\begin{smallmatrix}m \\ l\end{smallmatrix})$ is a decreasing function of $l$ when $l\geq m/2$ , for every $i$ and $j$ , we have

\begin{equation*}\begin{pmatrix}n-1 \\ n-i-j\end{pmatrix}\leq \begin{pmatrix}n-1 \\ n-d-q\end{pmatrix},\end{equation*}

because $n-i-j\geq n-d-q \geq n/2$ . Using again Stirling’s approximation, we deduce that

\begin{equation*}\begin{pmatrix}n-1 \\ n-d-q\end{pmatrix}\approx \big ((x+\epsilon )^{x+\epsilon }(1-x-\epsilon )^{1-x-\epsilon }\big )^{-n}.\end{equation*}

We can now conclude that

\begin{equation*}\dot {a}_{n,2d-2-x,\epsilon }\lesssim \dfrac {(2d-1)^{(2d-1)n}}{(x+\epsilon )^{(2x+2\epsilon )n} (1-x-\epsilon )^{(1-x-\epsilon )n}(2d-1-x)^{(2d-1-x)n}}.\end{equation*}

Taking $n$ th roots and letting $n\to \infty$ and $\epsilon \to 0$ we obtain

\begin{align*}\dot {a}_{2d-2-x}\leq \dfrac {(2d-1)^{2d-1}}{x^{2x} (1-x)^{1-x}(2d-1-x)^{2d-1-x}}. \end{align*}

Since a site interface is also a lattice site animal and $\partial P\subset \partial _V P$ , we obtain the following result.

Corollary 8.3. Consider some $0\leq x \leq 1$ , and let $y=\min \{x,1/2\}$ . Then

\begin{equation*}\dot {b}_{2d-2-x}({\mathbb {Z}}^d) \leq \dfrac {(2d-1)^{2d-1}}{y^y (1-y)^{1-y} x^x (2d-1-x)^{2d-1-x}}.\end{equation*}

In particular, $\dot{b}_{2d-2}({\mathbb{Z}}^d)=1$ .

We are now ready to prove Theorem 8.1.

Proof of Theorem 8.1 . For every $0\leq x\leq 1$ , we let

\begin{equation*}g_d(x)=\dfrac {(2d-1)^{2d-1}}{y^y (1-y)^{1-y} x^x (2d-1-x)^{2d-1-x}},\end{equation*}

where $y=\min \{x,1/2\}$ . It is not hard to see that there is a constant $C\gt 0$ such that $x^{-x}\leq C$ for every $x\in [0,1]$ , and

\begin{equation*}\dfrac {1}{y^y(1-y)^{1-y}}\leq C\end{equation*}

for every $y\in [0,1/2]$ . Moreover, for every $x\in [0,1]$ we have

\begin{equation*}\dfrac {(2d-1)^{2d-1}}{(2d-1-x)^{2d-1-x}}\leq \dfrac {(2d-1)^{2d-1}}{(2d-2)^{2d-1-x}}\end{equation*}

by the monotonicity of $2d-1-x$ as a function of $x$ , and

\begin{equation*}\dfrac {(2d-1)^{2d-1}}{(2d-2)^{2d-1-x}}=\dfrac {2d-1}{(2d-2)^{1-x}}\Big (1+\dfrac {1}{2d-2}\Big )^{2d-2}\leq \dfrac {2d-1}{(2d-2)^{1-x}}e.\end{equation*}

Thus,

\begin{equation*}g_d(x)\leq C^2 e \dfrac {2d-1}{(2d-2)^{1-x}}.\end{equation*}

Since $\dfrac{2d-1}{(2d-2)^{1-x}}$ is an increasing function of $x$ , it follows by Lemma 8.2 that for every

\begin{equation*}x\leq z\,:\!=1-\dfrac {C^2}{\log \big (2d-2\big )}\end{equation*}

we have

\begin{equation*}\dot {a}_{2d-2-x}({\mathbb {Z}}^d)\leq g_d(x)\leq C^2 e\dfrac {2d-1}{(2d-2)^{1-x}}\leq C^2 e\dfrac {2d-1}{(2d-2)^{1-z}}=\\ C^2e^{1-C^2}(2d-1).\end{equation*}

Using the standard inequality $e^{C^2}\geq 1+ C^2$ we obtain $e^{-C^2}\leq 1/(1+C^2)$ , hence

\begin{equation*}C^2e^{1-C^2}(2d-1)\leq \dfrac {C^2 e}{1+C^2}(2d-1).\end{equation*}

Plugging $r=2d-2-z$ in (13) we obtain $f(2d-2-z)=2de-5e/2+O(1/\log (d))$ , and so

(21) \begin{align} \dot{a}_{2d-2-x}({\mathbb{Z}}^d)\lt f(2d-2-z) \end{align}

for every $d$ large enough. On the other hand, for every $r\leq 2d-2-z$ we have $\dot{a}_r({\mathbb{Z}}^d)\leq f(2d-2-z)$ by (18), hence

\begin{equation*}\dot {a}({\mathbb {Z}}^d)\leq f(2d-2-z)=2de-5e/2+O(1/\log (d))\end{equation*}

by (4.3) for every $d$ large enough (recall that lattice site animals coincide with site interfaces for a special choice of a basis of the cycle space), which proves our claim.

Combining Theorem 8.1 with (10) yields the following lower bound for ${\dot{p}_c}({\mathbb{Z}}^d)$ .

Theorem 8.4. ${\dot{p}_c}({\mathbb{Z}}^d)\geq \dfrac{1}{2d}+\dfrac{2}{(2d)^2}-O(1/d^2\log (d))$ .

Proof. It follows from (21) that $b_r\lt f(2d-2-z)\leq f(r)$ for every $r\geq 2d-2-z$ , where $z=1-\dfrac{C^2}{\log\! \big (2d-2\big )}$ and $C$ is the constant in the proof of Theorem 8.1. Since $b_{\dot{r}_d}({\mathbb{Z}}^d)=f(\dot{r}_d)$ , we obtain

\begin{equation*}\dot {r}_d\leq 2d-3+\dfrac {C^2}{\log\! \big (2d-2\big )}.\end{equation*}

Hence,

\begin{equation*}{\dot {p}_c}({\mathbb {Z}}^d)=\dfrac {1}{1+\dot {r}_d}\geq \dfrac {1}{2d-2+C^2/\log (2d-2)}.\end{equation*}

It is not hard to see

\begin{align*} \dfrac{1}{2d-2+C^2/\log (2d-2)}&=\dfrac{1}{2d}+\dfrac{2-C^2/\log (2d-2)}{2d\big (2d-2+C^2/\log (2d-2)\big )}\\ & = \dfrac{1}{2d}+\dfrac{2}{(2d)^2}-O(1/d^2\log (d)), \end{align*}

which proves the assertion.

We remark that the well-known inequality ${\dot{p}_c}({\mathbb{Z}}^d)\geq p_c({\mathbb{Z}}^d)$ [18] and the asymptotic expansion $p_c({\mathbb{Z}}^d)=\frac{1}{2d}+\frac{1}{(2d)^2}+O(1/d^3)$ , mentioned in the previous section, give a weaker lower bound on ${\dot{p}_c}({\mathbb{Z}}^d)$ .

Remark: In both Theorem 8.4 and (11) we made implicit use of (6), but it would have sufficed to use its variant for site lattice animals instead of interfaces. Thus adapting Delyon’s [11] result to site animals would have sufficed.

9. An analogue of the Cheeger constant for interfaces

In this section, we define a variant $I(G)$ of the Cheeger constant with the aim of using it to obtain new bounds for $p_c$ .

Before introducing the variant $I(G)$ , let us first recall the definition of the Cheeger constant, which has both an edge and a vertex variant. Given a graph $G$ and a finite set of vertices $S$ , we define the edge boundary $\partial _E S$ of $S$ to be the set of edges of $G$ with one end vertex in $S$ and one not in $S$ . The vertex boundary $\partial _V S$ of $S$ is defined to be the set of vertices in $V\setminus S$ that have a neighbour in $S$ . The edge Cheeger constant of $G$ is defined as $h_E(G)=\inf _S \frac{|\partial _E S|}{|S|}$ , where the infimum is taken over all finite sets $S$ of vertices. The vertex Cheeger constant of $G$ is defined as $h_V(G)=\inf _S \frac{|\partial _V S|}{|S|}$ , where the infimum is taken again over all finite sets of vertices $S$ . In [8] Benjamini & Schramm proved that for all non-amenable graphs $G$ , $p_c(G)\leq \frac{1}{h_E(G)+1}$ and ${\dot{p}_c}(G)\leq \frac{1}{h_V(G)+1}$ .

Analogously to the Cheeger constant, we define the following quantities.

Definition 9.1. We define

\begin{equation*}I_E(G)\,:\!=\inf _{P} \frac {|\partial P|}{|P|} \qquad \textit {and} \qquad I_V(G)\,:\!=\inf _{Q} \frac {|\partial Q|}{|Q|},\end{equation*}

where the infimum ranges over all interfaces $P$ and site interfaces $Q$ , respectively.

It is possible that $I_E(G)\gt 0$ and $I_V(G)\gt 0$ while $h_E(G)=0$ and $h_V(G)=0$ . Examples of such graphs are all Cayley graphs of $1$ -ended amenable finitely presented groups. Indeed, it was proved that the cycle space of such graphs admits a basis consisting of cycles of bounded length [42], in which case $I_E(G)\gt 0$ and $I_V(G)\gt 0$ by [17, Lemma 10.9].

In the following theorem, we prove an upper bound on $p_c$ which is reminiscent of the result of Benjamini & Schramm. Our result applies to graphs for which

(22) \begin{align} &\text{ there exists a function} \,g(n) \text{ of sub-exponential growth with the property}\nonumber \\ &\text{that for every connected subgraph}\, H \text{ of} \,G \text{ with}\, n \text{ vertices, we have} |\partial ^V H| \leq g(n). \end{align}

This assumption is satisfied, for example, by the class of graphs $\mathcal{S}$ that we were working in the previous section for $g(n)=n^{\frac{d-1}{d}}$ . It has the following implication. Consider a vertex $o$ of $G$ and let $X$ be an infinite geodesic starting from $o$ . Let $P$ be a site interface of $o$ such that $|\partial P|=n$ . Then

(23) \begin{equation} P \,\text{contains one of the first} \,g(n) \text{ vertices of}\, X. \end{equation}

Theorem 9.2. Let $G$ be an $1$ -ended, $2$ -connected graph $G$ satisfying (22). Then we have

\begin{equation*}p_c(G)\leq \frac {1}{I_E(G)+1} \qquad \text {and} \qquad {\dot {p}_c}(G)\leq \frac {1}{I_V(G)+1}.\end{equation*}

Proof. We will prove the assertion for bond percolation. The case of site percolation is similar.

If $I_E(G)=0$ there is nothing to prove, so let us assume that $I_E(G)\gt 0$ . Let $q=\frac{1}{I_E(G)+1}$ and $r=1/{I_E(G)}$ . We claim that for every $p\gt q$ the expected number of occurring multi-interfaces of boundary size $n$ decays exponentially in $n$ . Indeed, let $\mathcal{P}_{n}$ be the (random) number of occurring multi-interfaces $P$ with $|\partial P|=n$ . Notice that

(24) \begin{equation} |P|\leq rn \text{ for every multi-interface} \,P \text{ with}\, |\partial P|=n, \end{equation}

hence $\mathcal{P}_{n}\leq G(n)$ , where $G(n)=e^{o(n)}$ , because at most $g(k)$ interfaces of size smaller that $k$ can occur in any percolation configuration $\omega$ . Indeed, we can choose $G(n)=p(rn)\max \{g(n_1)\ldots g(n_i)\}$ , where the maximum ranges over all possible partitions of $rn$ . It is not hard to see that $G(n)=e^{o(n)}$ .

Now for any $p\gt q$ and every $m\leq rn$ we have

\begin{gather*} p^m (1-p)^n=q^m (1-q)^n (p/q)^m \Big (\dfrac{1-p}{1-q}\Big )^n \leq \\ q^m (1-q)^n (p/q)^{rn} \Big (\dfrac{1-p}{1-q}\Big )^n =q^m (1-q)^n \big (f(r)\big )^n p^{rn} (1-p)^n, \end{gather*}

which implies that

(25) \begin{equation} \mathbb E_p(\mathcal{P}_n)\leq \mathbb E_q(\mathcal{P}_n) \big (f(r)\big )^n p^{rn} (1-p)^n \leq G(n) \big (f(r)\big )^n p^{rn} (1-p)^n. \end{equation}

Notice that $f(r) p^r (1-p)\lt 1$ , which proves our claim.

The fact that $\mathbb E_p(\mathcal{P}_n)$ decays exponentially in $n$ implies that the sum

\begin{equation*}\sum _{n=1}^\infty \sum _{\substack {P\in \mathcal {MI} \\ |\partial P|=n}} (-\!1)^{c(P)+1} {\mathbb {P}}_p(\text {$P$ occurs})\end{equation*}

converges absolutely, where $\mathcal{MI}$ is the set of multi-interfaces, and $c(P)$ is the number of component interfaces of $P$ . The inclusion-exclusion principle then implies that we can express $1-\theta$ as

\begin{equation*}1-\theta (p)=\sum _{n=1}^\infty \sum _{\substack {P\in \mathcal {MS} \\ |\partial P|=n}} (\!-\!1)^{c(P)+1} {\mathbb {P}}_p(P\ \text {occurs})\end{equation*}

for every $p\gt \frac{1}{I_E(G)+1}$ . We claim that the latter sum is an analytic function on $\Big(\frac{1}{I_E(G)+1},1\Big]$ . To prove this, we will use [17, Corollary 4.14], which states that any such expression is analytically provided the following two conditions are satisfied. Firstly, the event $\{P\ \text{occurs}\}$ should depend on $\Theta (|\partial P|)$ edges for every $P\in \mathcal{MS}$ , and secondly, for every $q\in \Big(\frac{1}{I_E(G)+1},1\Big)$ , there exists $0\lt c=c(q)\lt 1$ such that

\begin{equation*}\sum _{\substack {P\in \mathcal {MS} \\ |\partial P|=n}} (-\!1)^{c(P)+1} {\mathbb {P}}_p(\text {$P$ occurs})=O(c^n)\end{equation*}

for every $p\in (q,1)$ . In our case, the first condition follows from (24). The second condition follows from (25) and the fact that for every $q\in \Big(\frac{1}{I_E(G)+1},1\Big)$ , there exists $0\lt c=c(q)\lt 1$ such that $f(r) p^r (1-p)\leq c$ for every $p\in (q,1)$ . We can thus deduce that $\theta$ is analytic on the interval $\Big(\frac{1}{I_E(G)+1},1\Big]$ . Since $\theta$ is not analytic at $p_c$ , it follows that $p_c(G)\leq \frac{1}{I_E(G)+1}$ .

Remark 9.3. There is an alternative way to prove Theorem 9.2, without showing that $\theta$ is analytic, by means of (24) and a Peierls-type of argument. However, this alternative way is not simpler. We emphasise that the exponential decay of $\mathbb E_p(\mathcal{P}_n)$ does not imply, in general, that $p\gt p_c$ , as it can happen that $\mathbb E_p(\mathcal{P}_n)$ decays exponentially for some $p\lt p_c$ .

Clearly $I_E(G)\geq h_E(G)$ and $I_V(G)\geq h_V(G)$ , hence the above theorem gives an alternative proof of the result of Benjamini & Schramm mentioned above.

Question 9.4. For which (transitive) non-amenable graphs does the strict inequality $I_E(G)\gt h_E(G)$ ( $I_V(G)\gt h_V(G)$ ) hold?

It has been recently proved that $I_V(G)\gt h_V(G)$ holds for the $d$ -regular triangulations and quadrangulations of the hyperbolic plane [23].

10. Strict inequalities

As we already observed, interfaces are a special species of lattice animals. In this section, we will show that there are exponentially fewer interfaces than lattice animals for a large class of graphs. Building on this result, we will then show that the strict inequality $\dot{p}_c\lt \frac{1}{h_V+1}$ holds for a large class of non-amenable graphs. It will be more convenient for us to work with the site variants of interfaces and lattice animals.

We start by introducing some notation regarding site interfaces on general graphs. Consider an $1$ -ended, $2$ -connected, bounded degree graph $G$ . Furthermore, assume that both P5 and (22) are satisfied. For example, we can take $G$ to be a Cayley graph of an $1$ -ended, finitely presented group. We fix a basis of the cycle space consisting of cycles of bounded length and we consider the family of site interfaces associated with this basis. As we are working with a general graph which might not have any symmetries, the number of site interfaces might depend on the base vertex $o$ . For this reason, given a vertex $o$ of $G$ , we define $\dot{b}_{n,o}=\dot{b}_{n,o}(G)$ to be the number of site interfaces $P$ of $o$ with $|P|=n$ and we let $\dot{b}_n=\dot{b}_n(G)\,:\!=\sup _{o\in V(G)} \dot{b}_{n,o}$ . We now define $\dot{b}=\dot{b}(G)\,:\!=\limsup _{n\to \infty } \dot{b}^{1/n}_n$ .

As above, given a vertex $o$ of $G$ , we define $\dot{a}_{n,o}=\dot{a}_{n,o}(G)$ as the number of lattice site animals containing $o$ with $n$ vertices and we let $\dot{a}_n=\dot{a}_n(G)\,:\!=\sup _{o\in V(G)} \dot{a}_{n,o}$ . We now define $\dot{a}=\dot{a}(G)\,:\!=\limsup _{n\to \infty } \dot{a}^{1/n}_n$ .

For every vertex $v$ of $G$ , we let $\mathcal{P}_v$ be the set of basic cycles containing $v$ and we let $C_v$ be the union of all cycles in $\mathcal{P}_v$ . Using an argument similar to that in the proof of Kesten’s pattern theorem for self-avoiding walks [28], we will prove that the following holds.

Theorem 10.1. Let $G$ be an $1$ -ended, $2$ -connected, bounded degree graph $G$ satisfying P5 and (22). Then $\dot{b}(G)\lt \dot{a}(G)$ .

Proof. Consider a site interface $P$ of $o$ of size $n$ . We will introduce a local operation that turns $P$ into a lattice site animal that is not a site interface. To this end, let $l$ be the length of the longest cycle in $\mathcal{P}$ . Consider a set of vertices $S$ of $P$ with the property that any two vertices in $S$ are at distance at least $2l+1$ apart, and $S$ is a maximal set with respect to this property. It is not hard to see that the graphs $C_v$ , $v\in S$ are pairwise disjoint. Moreover, we have $|S|\geq n/d^{4l+2}$ , where $d$ is the maximal degree of $G$ , because the maximality of $S$ implies that any vertex of $P$ is at distance at most $4l+2$ from some vertex in $S$ .

Let $0\lt \varepsilon \lt 1/d^{4l+2}$ . For each subset $T$ of $S$ of cardinality $m=\left \lfloor{\varepsilon n}\right \rfloor$ , we let $P(T)=(\cup _{v\in T}C_v)\cup P$ . Recall that by (iv), a vertex $v$ is included in $P$ only if there is a $\mathcal{P}$ -path in $G\setminus \partial P$ connecting $v$ to $\vec{\partial P^{D}}$ , hence $C_v$ is not contained entirely in $P$ . It follows that among the vertices in $S$ , only those in $T$ have the property that $C_v$ is contained in $P(T)$ . Thus the graphs $P(T)$ are pairwise distinct and there are $(\begin{smallmatrix}|S| \\ m\end{smallmatrix})$ of them.

Our aim now is to find a lower bound for the cardinality of the set

\begin{equation*}Y_n\,:\!=\bigcup _{P} \{P(T) \mid T\subset S, |T|=m\}.\end{equation*}

To this end, we need to count the number of pre-images of each $P(T)$ . Let $P^{\prime}$ be a site interface of size $n$ and $T^{\prime}$ be a set of vertices of $P^{\prime}$ such that $P^{\prime}(T^{\prime})=P(T)$ . Notice that any vertex of $T^{\prime}$ needs to be at distance at most $2l$ from some vertex in $T$ . Hence $P^{\prime}$ coincides with $P$ on vertices at distance at most $3l$ from some vertex in $T$ . Thus there are at most $2^{d^{3l}m}$ possibilities for $P^{\prime}$ and $T^{\prime}$ .

Overall, we obtain

\begin{equation*}|Y_n|\geq \dfrac {\bigg(\begin{array}{l}m \\ k\end{array}\bigg)}{2^{d^{3l}m}}\dot {b}_{n,o},\end{equation*}

where $r=\left \lceil{n/d^{4l+2}}\right \rceil$ . Using Stirling’s approximation $N!=N^Ne^{-N+o(N)}$ , we obtain

\begin{equation*}{\bigg(\begin{array}{l}m \\ k\end{array}\bigg)}=\dfrac {r^r e^{o(n)}}{m^m(r-m)^{r-m}}\geq \Big (\dfrac {r}{m}\Big )^m e^{o(n)}=\Big (\dfrac {1}{\varepsilon d^{4l+2}}\Big )^{\varepsilon n+o(n)}.\end{equation*}

We can now deduce that

\begin{equation*}|Y_n|\geq \Big (\dfrac {1}{\varepsilon C}\Big )^{\varepsilon n+o(n)}\dot {b}_{n,o},\end{equation*}

where $C=2^{d^{3l}}d^{4l+2}$ . Choosing $\varepsilon =\big (C(2\dot{b})^{d^l}\big )^{-1}$ we obtain that

\begin{equation*}|Y_n|\geq (2\dot {b})^{d^l \varepsilon n+o(n)}\dot {b}_{n,o}.\end{equation*}

We claim that

\begin{equation*}\dot {a}_{k,v}\geq (2\dot {b})^{d^l \varepsilon n+o(n)}\dot {b}_{n,o},\end{equation*}

for some $n\leq k \leq n+d^l m$ and some vertex $v$ . Indeed, the size of each element of $Y_n$ varies between $n$ and $n+d^l m$ , so for some $n\leq k \leq n+d^l m$ , the number of elements of $Y_n$ of size $k$ is at least $(2\dot{b})^{d^l \varepsilon n+o(n)}\dot{b}_{n,o}$ . Now (23) implies that for some vertex $v$ , the number of elements of $Y_n$ of size $k$ that contain $v$ is at least $(2\dot{b})^{d^l \varepsilon n+o(n)}\dot{b}_{n,o}$ , which proves the claim.

Choosing some $o$ that maximises $\dot{b}_{n,o}$ , we obtain that

\begin{equation*}\dot {a}_{k,v}\geq 2^{d^l \varepsilon n} \dot {b}^{(1+d^l \varepsilon )n+o(n)}\end{equation*}

for some $n\leq k \leq n+d^l m$ and some vertex $v=v(n)$ . Taking the $k$ th root and letting $k$ tend to infinity, we obtain that

\begin{equation*}\dot {a}\geq 2^{\frac {d^l\varepsilon }{1+d^l\varepsilon }}\dot {b}\end{equation*}

because $k\leq n+d^l m\leq (1+d^l \varepsilon )n$ . This proves the desired result.

We will now assume that $G$ is a non-amenable graph. As already mentioned, it is a well-known result of Benjamin & Schramm that $\dot{p}_c(G)\leq 1/(h_V+1)$ [8]. We prove that this inequality is in fact strict.

Theorem 10.2. Let $G$ be an $1$ -ended, $2$ -connected, bounded degree, non-amenable graph $G$ satisfying P5 . Then $\dot{p}_c(G)\lt \frac{1}{h_V(G)+1}$ .

Proof. We will prove that for the values of $p$ in a neighbourhood of $1/(h_V(G)+1)$ , the expected number of occurring site interfaces of size $n$ decays exponentially in $n$ . This easily implies the theorem as for example, we can argue as in the proof of Theorem 9.2 to deduce that $\theta$ is analytic in a neighbourhood of $1/(h_V(G)+1)$ .

Consider some $\delta \in (0,1/h_V)$ and let $I_{n,\delta }$ be the set of site interfaces $P$ such that $|\partial P|=n$ and $|P|\geq (1/h_V-\delta ) n$ . We will show that for a small enough $\delta$ , the expected number of occurring elements of $I_{n,\delta }$ decays exponentially. Arguing as in the proof of Theorem 10.1 and using the notation introduced there, we can associate to $I_{n,\delta }$ a set $Y_{n,\delta }$ of connected subgraphs such that

\begin{equation*}|Y_{n,\delta }|\geq \Big (\dfrac {1}{\varepsilon C}\Big )^{\varepsilon (1/h_V-\delta ) n+o(n)}|I_{n,\delta }|.\end{equation*}

Given $P\in I_{n,\delta }$ , $Q\in Y_{n,\delta }$ with $P$ being a pre-image of $Q$ , we would like to show that ${\mathbb{P}}_p(P \text{ occurs})$ is not much larger than ${\mathbb{P}}_p(Q \text{ is open and } \partial _V Q \text{ is closed})$ (the latter is the probability that $Q$ is a cluster). In order to do this, we need to estimate the size of $\partial _V Q$ . To this end, let $D$ be the union of all the finite components of $G\setminus \partial P$ . By (ii) and (iv), $P$ is contained in $D$ and $\partial _V D=\partial P$ . Notice that

\begin{equation*}n=|\partial P|\geq h_V\big (|P|+\big (|D|-|P|\big )\big )\geq n-h_V\delta n+h\big (|D|-|P|\big ),\end{equation*}

which implies that

(26) \begin{equation} |D|-|P|\leq \delta n. \end{equation}

Since $Q$ can be obtained from $P$ by adding at most $d^l$ vertices at $\left \lfloor{\varepsilon |P|}\right \rfloor$ places, we obtain that $|Q| \leq (1+d^l \varepsilon )|P|$ . Moreover, by considering the size of the neighbourhood of $Q\setminus P$ , we see that

\begin{equation*}|\partial _V Q| \leq |\partial _V P|+d^{l+1}\varepsilon |P|\leq |\partial P|+|D|-|P|+d^{l+1}\varepsilon |P|,\end{equation*}

where the term $|D|-|P|$ comes from the fact that $\partial _V P\setminus \partial P\subset D\setminus P$ . Using (26) and the last inequality, we find that

\begin{equation*}{\mathbb {P}}_p(P \text { occurs})\leq \big (p(1-p)\big )^{-K(\delta +\varepsilon )n}{\mathbb {P}}_p(Q \text { is open and } \partial _V Q \text { is closed})\end{equation*}

for a certain constant $K\gt 0$ . We can now choose $\delta =\varepsilon$ small enough that for every $p\in [h_V/2,(h_V+1)/2]$ we have

\begin{equation*}\sum _{P\in I_{n,\delta }}{\mathbb {P}}_p(P \text { occurs})\leq 2^{-\varepsilon n} \sum _{Q\in Y_{n,\delta }} {\mathbb {P}}_p(Q \text { is open and } \partial _V Q \text { is closed}).\end{equation*}

Now the non-amenability of $G$ implies that each $Q\in Y_{n,\delta }$ contains one of the first $2^{o(n)}$ vertices of $X$ , hence $\sum _{Q\in Y_{n,\delta }}{\mathbb{P}}_p(Q \text{ is open and } \partial _V Q \text{ is closed})=2^{o(n)}$ which in turn implies that $\sum _{P\in I_{n,\delta }}{\mathbb{P}}_p(P \text{ occurs})$ decays exponentially in $n$ .

On the other hand, it follows from Lemma 4.7 that for every $x\gt 0$ , the expected number of occurring interfaces $P$ with $|\partial P| =n$ and $|P|\lt \big (\frac{p}{1-p}-x\big )n$ decays exponentially in $n$ . Hence for every $p\gt q\,:\!= \frac{1-h\delta }{h+1-h\delta }$ , the expected number of occurring interfaces $P$ with $|\partial P| =n$ and

\begin{equation*}|P|\lt \left (\frac {1}{h}-\delta \right ) n=\frac {qn}{1-q}\end{equation*}

under ${\mathbb{P}}_p$ , decays exponentially in $n$ , because $\frac{q}{1-q}\lt \frac{p}{1-p}$ . Since we have $q\lt 1/(h+1)$ , the latter exponential decay holds at a neighbourhood of $1/(h+1)$ . This completes the proof.

11. Conclusion

In this paper, we obtained basic properties of the function $b_r(G)$ , and connected it to percolation theory and the enumeration of lattice animals. Many questions about $b_r(G)$ are left open, of which we mention just a few. We remarked that $\max _r b_r(G)$ is interesting, as it coincides with $b(G)$ , which lower bounds the growth rate $a(G)$ of lattice animals. We expect that this maximum is attained at a single point $r= r_{max}$ . What can be said about $r_{max}$ ? Is it always greater than $r(p_c)$ ? Is their ratio, or some other expression, independent of the lattice $G$ once the dimension is fixed?

We observed that $b_r$ is a continuous, almost everywhere differentiable function of $r$ . Are stronger smoothness conditions satisfied? Is it smooth/analytic at every $r\neq r(p_c), r(1-p_c)$ ?