1 Introduction
Suppose that we are given a finite simple graph $\Gamma = (V,E)$ and we are asked to count its number of independent sets. An independent set is a subset $I \subseteq V$ such that $(v,v') \notin E$ (that is, $(v,v')$ is not an edge) for all $v,v' \in I$ . For example, if $\Gamma $ is the $4$ -cycle $C_4$ with $V = \{v_1,v_2,v_3,v_4\}$ and $E = \{(v_1,v_2),(v_2,v_3),(v_3,v_4),(v_4,v_1)\}$ , it can be checked that there are exactly seven different independent sets, namely $\emptyset $ , $\{v_1\}$ , $\{v_2\}$ , $\{v_3\}$ , $\{v_4\}$ , $\{v_1,v_3\}$ , and $\{v_2,v_4\}$ . A common generalization of this question is to ask for the ‘number’ of weighted independent sets in $\Gamma $ : given a parameter $\unicode{x3bb}> 0$ —usually called activity or fugacity—we ask for the value of the summation
where $X(\Gamma )$ denotes the collection of all independent sets in $\Gamma $ and $\lvert I \lvert $ , the cardinality of a given independent set I. Notice that we recover the original problem—that is, to compute $\lvert X(\Gamma ) \rvert $ —if we set $\unicode{x3bb} = 1$ . The sum $Z_\Gamma (\unicode{x3bb} )$ corresponds to the normalization factor of the probability distribution $\mathbb {P}_{\Gamma ,\unicode{x3bb} }$ on $X(\Gamma )$ that assigns to each $I \in X(\Gamma )$ a probability proportional to $\unicode{x3bb} ^{\lvert I \rvert }$ , that is, the so-called partition function (also known as the independence polynomial) of the well-known hardcore model from statistical physics.
In general, it is not possible to compute exactly $Z_\Gamma (\unicode{x3bb} )$ efficiently [Reference Luby and Vigoda31], even for the case $\unicode{x3bb} = 1$ [Reference Xia, Zhao, Cai, Cooper and Li56]; technically, to compute $Z_\Gamma (\unicode{x3bb} )$ is an $\mathrm {NP}$ -hard problem and to compute $\lvert X(\Gamma ) \rvert $ is a $\#\mathrm {P}$ -complete problem. Therefore, one may attempt to at least find ways to approximate $Z_\Gamma (\unicode{x3bb} )$ efficiently.
In recent years, there has been a great deal of attention given to the complexity of approximating partition functions of spin systems (e.g., see [Reference Barvinok4]). Among these systems, the hardcore model, possibly together with the Ising model [Reference Sinclair, Srivastava and Thurley47], occupies the most important place. One of the most notable results, due to Weitz [Reference Weitz55], and then Sly [Reference Sly48] and Sly and Sun [Reference Sly and Sun49], is the existence of a computational phase transition for having a fully polynomial-time approximation scheme (FPTAS) for the approximation of $Z_\Gamma (\unicode{x3bb} )$ . In simple terms, Weitz developed an FPTAS, a particular kind of efficient deterministic approximation algorithm, on the family of finite graphs with bounded degree $\Delta $ provided $\unicode{x3bb} < \unicode{x3bb} _c(\Delta )$ , where $\unicode{x3bb} _c(\Delta ) := {(\Delta -1)^{(\Delta -1)}}/{(\Delta -2)^{\Delta }}$ denotes the critical activity for the hardcore model on the $\Delta $ -regular tree $\mathbb {T}_\Delta $ . Conversely, a couple of years later, Sly and Sun managed to prove that the existence of even a fully polynomial-time randomized approximation scheme (FPRAS)—which is a probabilistic and therefore weaker version of an FPTAS—for $\unicode{x3bb}> \unicode{x3bb} _c(\Delta )$ would imply that $\mathrm {NP} = \mathrm {RP}$ , the equivalence of two well-known computational complexity classes which are widely believed to be different [Reference Arora and Barak2].
The work of Weitz exploited a technique based on trees of self-avoiding walks and a special notion of correlation decay known as strong spatial mixing that, in particular, holds when the graph is $\mathbb {T}_\Delta $ and $\unicode{x3bb} < \unicode{x3bb} _c(\Delta )$ . Later, Sinclair et al [Reference Sinclair, Srivastava, Štefankovič and Yin46] studied refinements of Weitz’s result by considering families of finite graphs parameterized by their connective constant instead of their maximum degree, and established that there exists an FPTAS for $Z_\Gamma (\unicode{x3bb} )$ for families of graphs with connective constant bounded by $\mu $ , whenever $\unicode{x3bb} < {\mu ^\mu }/{(\mu -1)^{(\mu +1)}}$ .
Now, if $\Gamma $ is an infinite graph, most of these concepts stop making sense. One way to deal with this issue is by choosing an appropriate normalization and by using the DLR formalism. The idea is roughly the following: suppose that we have a sequence $\{\Gamma _n\}_n$ of finite subgraphs that ‘exhausts’ $\Gamma $ in some way. This sequence induces two other sequences: a sequence $\{Z_{\Gamma _n}(\unicode{x3bb} )\}_n$ of partition functions and a sequence $\{\mathbb {P}_{\Gamma _n,\unicode{x3bb} }\}_n$ of probability distributions. A way to extend the idea of ‘number of weighted independent sets (per site)’ in $\Gamma $ is by considering the sequence $\{Z_{\Gamma _n}(\unicode{x3bb} )^{1/\lvert \Gamma _n \rvert }\}_n$ and hoping that it converges. Under the right assumptions on $\Gamma $ and $\{\Gamma _n\}_n$ , this is exactly the case and something similar happens to $\{\mathbb {P}_{\Gamma _n,\unicode{x3bb} }\}_n$ . Moreover, there is an intimate connection between the properties of the limit measures and our ability to estimate the value of $\lim _n \lvert \Gamma _n \rvert ^{-1} \log Z_{\Gamma _n}(\unicode{x3bb} )$ , that is, to ‘approximately count’ it. We denote this limit—which, a priori, may depend on the sequence $\{\Gamma _n\}_n$ —by $f_{\{\Gamma _n\}_n}(\Gamma ,\unicode{x3bb} )$ and call it the free energy of the hardcore model $(\Gamma ,\unicode{x3bb} )$ , one of the most crucial quantities in statistical physics [Reference Baxter6, Reference Georgii17, Reference Simon44].
It can be checked that if $\Gamma $ is finite, to approximate the partition function $Z_\Gamma (\unicode{x3bb} )$ with a multiplicative error (in polynomial time) is equivalent to approximate the free energy $f_{\{\Gamma \}_n}(\Gamma ,\unicode{x3bb} )$ —where $\{\Gamma \}_n$ is the constant sequence which immediately exhausts the graph—with an additive error [Reference Liu, Sinclair and Srivastava30] (in polynomial time). Therefore, the problem of approximating $f_{\{\Gamma \}_n}(\Gamma ,\unicode{x3bb} )$ recovers the problem of approximating the partition function in the finite case and, at the same time, extends the problem to the infinite setting.
The main goal of this paper is to establish a computational phase transition for the free energy on ensembles of—possibly infinite—hardcore models. In other words, we aim to prove the existence of an efficient additive approximation algorithm for the free energy when the activity is low and to establish that there is no efficient approximation algorithm for the free energy when the activity is high, unless $\mathrm {NP} = \mathrm {RP}$ .
There have been many recent works related to the study of correlation decay properties and their relation to approximation algorithms for the free energy (and related quantities such as pressure, capacity, and entropy) in the infinite setting [Reference Briceño8, Reference Gamarnik and Katz16, Reference Marcus and Pavlov34–Reference Marcus and Pavlov36, Reference Pavlov40, Reference Wang, Yin and Zhong53]. In this work, we put all these results in a single framework, which also encompasses the results from Weitz, Sly and Sun, and Sinclair et al, and at the same time generalizes them.
In 2009, Gamarnik and Katz [Reference Gamarnik and Katz16] introduced what they called the sequential cavity method, which can be regarded as a sort of infinitary self-reducibility property [Reference Jerrum, Valiant and Vazirani24]. Combining this method with Weitz’s results, they managed to prove that the free energy of the hardcore model in the Cayley graph of $\mathbb {Z}^d$ with canonical generators admits a (deterministic) $\epsilon $ -additive approximation algorithm that runs in time polynomial in $\epsilon ^{-1}$ whenever $\unicode{x3bb} < \unicode{x3bb} _c(2d)$ , where $2d$ is the maximum degree of the graph. Related results were also proven by Pavlov in [Reference Pavlov40], who developed an approximation algorithm for the hard square entropy, that is, the free energy of the hardcore model in the Cayley graph of $\mathbb {Z}^2$ with canonical generators and activity $\unicode{x3bb} = 1$ . Later, there were also some explorations due to Wang et al [Reference Wang, Yin and Zhong53] in Cayley graphs of $\mathbb {Z}^2$ with respect to other generators (e.g., the non-attacking kings system) in the context of information theory and algorithms for approximating capacities.
In this paper, we prove that all these results fit and can be generalized to hardcore models $(\Gamma ,\unicode{x3bb} )$ such that: (1) $\Gamma $ is a locally finite graph; (2) $G \curvearrowright \Gamma $ is free and almost transitive for some countable amenable subgroup $G \leq \mathrm {Aut}(\Gamma )$ ; and (3) $\unicode{x3bb} : V \to \mathbb {Q}_{>0}$ is a—not necessarily constant—G-invariant activity function. In addition, for the algorithmic implications, we assume that G satisfies some of the recursion-theoretic assumptions described below. Given this setting, we consider a Følner sequence $\{F_n\}_n$ , a fundamental domain $U_0 \subseteq V$ of $G \curvearrowright \Gamma $ , and the sequence of finite subgraphs $\{\Gamma _n\}_n$ induced by $\{F_nU_0\}_n$ . First, we show that $f_{\{\Gamma _n\}_n}(\Gamma ,\unicode{x3bb} )$ is independent of $\{F_n\}_n$ and $U_0$ , and that the limit $f_{\{\Gamma _n\}_n}(\Gamma ,\unicode{x3bb} )$ —which we denote by $f_G(\Gamma ,\unicode{x3bb} )$ to emphasize the independence of $\{F_n\}_n$ and $U_0$ —can be expressed as an infimum over some suitable family of finite subgraphs of $\Gamma $ . Next, based on results from [Reference Briceño9, Reference Gurevich and Tempelman20], we prove in Theorem 7.1 that $f_G(\Gamma ,\unicode{x3bb} )$ can be obtained as the pointwise limit of a Shannon–McMillan–Breiman-type ratio with regards to any Gibbs measure on $X(\Gamma )$ . In Theorem 7.5, we prove that if $\unicode{x3bb} $ is such that $(\Gamma ,\unicode{x3bb} )$ satisfies strong spatial mixing, then $f_G(\Gamma ,\unicode{x3bb} )$ corresponds to the evaluation of a random information function, based on ideas about random invariant orders and the Kieffer–Pinsker formula for measure-theoretical entropy introduced in [Reference Alpeev, Meyerovitch and Ryu1]. Then, in Theorem 7.6, using the previous representation theorem and the techniques from [Reference Weitz55], we provide a formula for $f_G(\Gamma ,\unicode{x3bb} )$ in terms of trees of self-avoiding walks in $\Gamma $ . These first three theorems can be regarded as a preprocessing treatment of $f_G(\Gamma ,\unicode{x3bb} )$ to obtain an arboreal representation of free energy to develop approximation techniques, but we believe that they are of independent interest.
Later, we consider a finitely generated amenable group G with a prescribed set of generators S such that its word problem can be solved in exponential time. This last requirement seems to be natural and many groups satisfy it (for example, any linear group, including all abelian, all nilpotent groups, and, more generally, all virtually polycyclic groups). Given a positive integer $\Delta $ and $\unicode{x3bb} _0> 0$ , we denote by $\mathcal {H}_G^\Delta (\unicode{x3bb} _0)$ the ensemble of hardcore models $(\Gamma ,\unicode{x3bb} )$ such that $G \curvearrowright \Gamma $ is free and almost transitive, the maximum degree of $\Gamma $ is bounded by $\Delta $ , and the values of $\unicode{x3bb} $ are bounded from above by $\unicode{x3bb} _0$ . Then, in Theorem 8.5, we establish the following algorithmic implication: if $\unicode{x3bb} _0 < \unicode{x3bb} _c(\Delta )$ , there exists an additive FPRAS on $\mathcal {H}_G^{\Delta }(\unicode{x3bb} _0)$ for $f_G(\Gamma ,\unicode{x3bb} )$ , where $\unicode{x3bb} _c(\Delta )$ denotes the critical activity on the $\Delta $ -regular tree $\mathbb {T}_\Delta $ . This can be considered as a confirmation in the amenable setting of the ‘algorithmic version’—as called in [Reference Weitz55]—of [Reference Sokal50, Conjecture 2.1]. In addition, under the extra assumption that G has a finite index linearly ordered subgroup $(H, \prec )$ such that its algebraic past $\Phi _\prec = \{g \in H: g \prec 1_G\}$ can be decided in exponential time, we prove that the algorithm can be chosen to be deterministic, that is, there exists an additive FPTAS. Groups that satisfy this extra condition include all finitely generated abelian groups, nilpotent groups like the Heisenberg group $H_3(\mathbb {Z})$ , and solvable groups like the Baumslag–Solitar groups $BS(1,n)$ . However, in Corollary 8.8, we observe that if $\unicode{x3bb} _0> \unicode{x3bb} _c(\Delta )$ , there is no additive FPRAS unless $\mathrm {NP} = \mathrm {RP}$ . In particular, we obtain that the results from Weitz, Sly, and Sun correspond to the special case when G is the trivial (and orderable) group.
By an additive FPRAS, we mean a probabilistic algorithm that given $(\Gamma ,\unicode{x3bb} )$ and $\epsilon> 0$ , outputs a number $\hat {f}$ such that $\lvert f_G(\Gamma ,\unicode{x3bb} ) - \hat {f} \rvert < \epsilon $ with probability greater than $3/4$ in time polynomial in $\lvert \Gamma / G \rvert $ and $\epsilon ^{-1}$ . Here, $\lvert \Gamma / G \rvert $ denotes the size of some (or any) fundamental domain of the action $G \curvearrowright \Gamma $ , and therefore, all the information we need to construct $\Gamma $ . However, by an additive FPTAS, we mean an additive FPRAS with success probability equal to $1$ instead of just $3/4$ . We assume throughout the paper that the standard functions and arithmetic operations of the numerical values involved can be computed exactly in one unit of time.
Finally, as an application in symbolic dynamics, we show how to use these results to establish representation formulas and efficient approximation algorithms for the topological entropy of nearest-neighbor subshifts of finite type with enough safe symbols. Also, we consider the pressure of single-site potentials with a vacuum state, which includes systems such as the Widom–Rowlinson model and some other weighted graph homomorphisms from $\Gamma $ to any finite graph, among others. These results can also be regarded as an extension of the works by Marcus and Pavlov in $\mathbb {Z}^d$ (see [Reference Marcus and Pavlov34–Reference Marcus and Pavlov36]), who developed additive approximation algorithms for the entropy and free energy (or pressure) of general $\mathbb {Z}^d$ -subshifts of finite type, with special emphasis in the case $d=2$ . We believe that these implications are relevant, especially in the light of results like that from Hochman and Meyerovitch. In [Reference Hochman and Meyerovitch23], Hochman and Meyerovitch proved that the set of topological entropies that a nearest-neighbor $\mathbb {Z}^2$ -subshift of finite type can achieve coincides with the set of non-negative right-recursively enumerable real numbers. This class of numbers includes numbers that are poorly computable or even not computable. In addition, we discuss the case of the monomer–dimer model and counting independent sets of line graphs, which is a special case that does not exhibit a phase transition. As a byproduct of our results, we also give sufficient conditions for the existence of a unique measure of maximal entropy for subshifts on arbitrary amenable groups.
We remark that our results—considering related ones, like those obtained by Gamarnik and Katz in [Reference Gamarnik and Katz16]—are novel in at least three aspects.
-
(1) Almost transitive framework. The generalization to the almost transitive case provides enough flexibility so that (i) other systems (such as subshifts of finite type, matchings, etc.) can be represented through reductions in terms of independent sets in suitable graphs and (ii) the measurement of (the size of) fundamental domains as a way to measure computational complexity provides a way to obtain a computational phase transition. These aspects—to our knowledge—are new, even in the relevant case $G = \mathbb {Z}^d$ , that is, the family of graphs such that $\mathbb {Z}^d$ acts almost transitively on them.
-
(2) Algorithms for graphs with exponential growth. Our approach, which provides polynomial time approximation algorithms, works for amenable groups not only of polynomial growth but also exponential growth. A relevant case that is fully explored in §8 is the family of Baumslag–Solitar groups $BS(1,n)$ for $n \geq 2$ , which have exponential growth but admit even a deterministic approximation algorithm for free energy.
-
(3) Lack of orderability. If a group does not have an orderable subgroup of finite index, it is less clear how to obtain a sequential cavity method as in [Reference Gamarnik and Katz16], which exploits the existence of an invariant deterministic order of the group at hand (like, for example, the lexicographic order in $\mathbb {Z}^d$ ). Our free energy representation formulas, in terms of invariant random orders, provide a way to develop randomized approximation algorithms for groups that are not necessarily orderable.
The paper is organized as follows: in §2, we introduce the basic concepts regarding graphs, homomorphisms, independent sets, group actions, Cayley graphs, and partition functions; in §3, we rigorously define free energy based on the notion of amenability and show some robustness properties of its definition; in §4, we define Gibbs measures and relevant spatial mixing properties; in §5, we develop the formalism based on trees of self-avoiding walks and discuss some of their properties; in §6, we present the formalism of invariant (deterministic and random) orders of a group; in §7, we prove Theorems 7.1, 7.5, and 7.6, which provide a randomized sequential cavity method that allows us to obtain an arboreal representation of free energy; in §8, we prove Theorem 8.5 and establish the algorithmic implications of our results; in §9, we provide reductions that allow us to translate the problem of approximating pressure of a single-site potential and the topological entropy of a subshift into the problem of counting independent sets, and discuss other consequences that are implicit in our results.
2 Preliminaries
2.1 Graphs
A graph will be a pair $\Gamma = (V,E)$ such that V is a countable set—the vertices—and $E \subseteq V \times V$ is a symmetric relation—the edges. Let $\leftrightarrow $ be the equivalence relation generated by E, that is, $v \leftrightarrow v'$ if and only if there exist $n \in \mathbb {N}_0$ and $\{v_i\}_{0 \leq i \leq \ell }$ such that $v = v_0$ , $v' = v_n$ , and $(v_i,v_{i+1}) \in E$ for every $0 \leq i < n$ . Denote by $n(v,v')$ the smallest n with this property. This induces a notion of distance in $\Gamma $ given by
Given a set $U \subseteq V$ , we define its boundary $\partial U$ as the set $\{v \in V: \mathrm {dist}_\Gamma (v,U) = 1\}$ , where $\mathrm {dist}_\Gamma (U,U') = \inf _{v \in U, v' \in U'} \mathrm {dist}_\Gamma (v,v')$ . In addition, given $\ell \geq 0$ and $v \in V$ , we define the ball centered at v with radius $\ell $ as $B_\Gamma (v,\ell ) := \{v' \in V: \mathrm {dist}_\Gamma (v,v') \leq \ell \}$ .
A graph $\Gamma $ is:
-
• loopless, if E is anti-reflexive (that is, there is no vertex related to itself);
-
• connected, if $v \leftrightarrow v'$ for every $v,v' \in V$ ; and
-
• locally finite, if every vertex is related to only finitely many vertices.
Sometimes we will write $V(\Gamma )$ and $E(\Gamma )$ —instead of just V and E—to emphasize $\Gamma $ .
2.2 Homomorphisms
Consider graphs $\Gamma _1$ and $\Gamma _2$ . A graph homomorphism is a map $g: V(\Gamma _1) \to V(\Gamma _2)$ such that
We denote by $\mathrm {Hom}(\Gamma _1,\Gamma _2)$ the set of graph homomorphisms from $\Gamma _1$ to $\Gamma _2$ .
A graph isomorphism is a bijective map $g: V(\Gamma _1) \to V(\Gamma _2)$ such that
If a map like this exists, we say that $\Gamma _1$ and $\Gamma _2$ are isomorphic, denoted by $\Gamma _1 \cong \Gamma _2$ .
A graph automorphism is a graph isomorphism from a graph $\Gamma $ to itself. We denote by $\mathrm {Aut}(\Gamma )$ the set of graph automorphisms of $\Gamma $ . This set is a group when considering composition $\circ $ as the group operation and the identity map $\mathrm {id}_\Gamma : V \to V$ as the identity group element $1_{\mathrm {Aut}(\Gamma )}$ . In this case, instead of writing $g_1 \circ g_2$ , we will simply write $g_1g_2$ to emphasize the group structure.
2.3 Independent sets
Given a subset $U \subseteq V$ , the induced subgraph by U, denoted $\Gamma [U]$ , is the graph with a set of vertices U and set of edges $E \cap (U \times U)$ . A subset $I \subseteq V$ is called an independent set if $\Gamma [I]$ has no edges. We can also represent an independent set by its indicator function, that is, by the map $x: V \to \{0,1\}$ so that
In addition, if we consider the finite graph $H_0 := (\{0,1\},\{(0,0),(0,1),(1,0)\})$ , then x can be also understood as a graph homomorphism from $\Gamma $ to $H_0$ (see Figure 1).
We denote by $X(\Gamma )$ the set of independent sets of $\Gamma $ . Notice that $X(\Gamma ) \subseteq \{0,1\}^{V}$ can be identified with the set $\mathrm {Hom}(\Gamma ,H_0)$ and that the empty independent set $0^{V}$ always belongs to $X(\Gamma )$ . Sometimes we will denote this independent set by $0^\Gamma $ .
2.4 Group actions
Let G be a subgroup of $\mathrm {Aut}(\Gamma )$ . Given $g \in G$ and $v \in V$ , the map $(g,v) \mapsto g \cdot v := g(v)$ is a (left) group action, this is to say, $1_G \cdot v = v$ and $(gg') \cdot v = g \cdot (g' \cdot v)$ for all $g' \in G$ , where $1_G = 1_{\mathrm {Aut}(\Gamma )}$ . In this case, we say that G acts on $\Gamma $ and denote this fact by $G \curvearrowright \Gamma $ .
The group G also acts on $\{0,1\}^{V}$ by precomposition. Given $g \in G$ and $x \in \{0,1\}^{V}$ , consider the map $(g,x) \mapsto g \cdot x := x \circ g^{-1}$ . A subset $X \subseteq \{0,1\}^{V}$ is called G-invariant if $g \cdot X = X$ for all $g \in G$ , where $g \cdot X := \{g \cdot x: x \in X\}$ . Clearly, if $x \in X(\Gamma )$ , then $g \cdot x$ and $g^{-1} \cdot x$ also belong to $X(\Gamma )$ , since $g \in \mathrm {Aut}(\Gamma )$ and $x \in \mathrm {Hom}(\Gamma ,H_0)$ . Therefore, $X(\Gamma )$ is G-invariant and the action $G \curvearrowright X(\Gamma )$ is well defined.
We will usually use the letter v to denote vertices in V, the letter g to denote graph automorphisms in G, and the letter x to denote independent sets in $X(\Gamma )$ . To distinguish the action of G on V from the action of G on $X(\Gamma )$ , we will write $g v$ instead of $g \cdot v$ , without risk of ambiguity.
The action $G \curvearrowright \Gamma $ is always faithful, that is, for all $g \in G \setminus \{1_G\}$ , there exists $v \in V$ such that $g v \neq v$ . The G-orbit of a vertex $v \in V$ is the set $Gv := \{g v: g \in G\}$ . The set of all G-orbits of $\Gamma $ , denoted by $\Gamma /G$ , is a partition of V and it is called the quotient of the action.
We say that a subset $\emptyset \neq U \subseteq V$ is dynamically generating if $GU = V$ , where $GF := \{g v: g \in F, v \in U\}$ for any $F \subseteq G$ , and a fundamental domain if it is also minimal, that is, if $U' \subsetneq U$ , then $GU' \subsetneq V$ . The action $G \curvearrowright \Gamma $ is almost transitive if $\lvert \Gamma /G \rvert < +\infty $ and transitive if $\lvert \Gamma /G \rvert = 1$ . A graph $\Gamma $ is called almost transitive (respectively transitive) if $\mathrm {Aut}(\Gamma ) \curvearrowright \Gamma $ is almost transitive (respectively transitive).
The index of a subgroup $H \leq G$ , denoted by $[G:H]$ , is the cardinality of the set of cosets $\{Hg: g \in G\}$ . We will usually consider subgroups of finite index. In this case, we have that $\lvert \Gamma /H \rvert = \lvert \Gamma /G \rvert [G:H]$ .
The G-stabilizer of a vertex $v \in V$ is the subgroup $\mathrm {Stab}_G(v) := \{g \in G: g v = v\}$ . Notice that, since $\mathrm {Stab}_G(gv) = g\mathrm {Stab}_G(v)g^{-1}$ for every $g \in G$ , we have that $\lvert \mathrm {Stab}_G(v) \rvert = \lvert \mathrm {Stab}_G(v') \rvert $ for all $v' \in Gv$ . If $\lvert \mathrm {Stab}_G(v) \rvert < \infty $ for all v, we say that the action is almost free, and if $\lvert \mathrm {Stab}_G(v) \rvert = 1$ (that is, if $\mathrm {Stab}_G(v) = \{1_G\}$ ) for all $v,$ we say that the action is free.
A relevant observation is that if we assume that $\Gamma $ is countable and $G \curvearrowright \Gamma $ is almost transitive and almost free, then G must be a countable group. In this work, we will only consider almost free and almost transitive actions. In this case, there exists a finite fundamental domain $U_0 \subseteq V$ such that $\lvert U_0 \rvert = \lvert \Gamma /G \rvert $ and, if $\Gamma $ is locally finite, then $\Gamma $ must have bounded degree, that is, there is a uniform bound on the number of vertices to which each vertex is related. In this case, we denote by $\Delta (\Gamma )$ the maximum degree among all vertices of the graph $\Gamma $ .
2.5 Transitive case: Cayley graphs
Consider a subset $S \subseteq G$ that we assume to be symmetric, that is, $S = S^{-1}$ , where $S^{-1} = \{s^{-1} \in S: s \in S\}$ . We define the (right) Cayley graph as $\mathrm {Cay}(G,S) = (V,E)$ , where
Cayley graphs are a natural construction used to represent groups in a geometric fashion. In this context, it is common to ask that $1_G \notin S$ , S to be finite, and S to be generating, that is, $G = \langle S \rangle $ , where
Groups that have a set S satisfying these conditions are called finitely generated. Notice that if $1_G \notin S$ , then $\mathrm {Cay}(G,S)$ is loopless; if S is finite, then $\mathrm {Cay}(G,S)$ has bounded degree; and if S is generating, then $\mathrm {Cay}(G,S)$ is connected. Now, suppose that $G \curvearrowright \Gamma $ is transitive (and free). Then, there exists a symmetric set $S \subseteq G$ such that
Indeed, it suffices to take $S = \{g \in G: (v,g v) \in E\}$ , where $v \in V$ is arbitrary (see [Reference Sabidussi42]).
We will be interested in Cayley graphs $\Gamma = \mathrm {Cay}(G,S)$ and their subgroup of automorphisms induced by group multiplication as a special and relevant case: given $g \in G$ , we can define $f_g: \Gamma \to \Gamma $ as $f_g(g') = g'g$ and it is easy to check that $f_g \in \mathrm {Aut}(\Gamma )$ . Then G acts (as a group, from the left) on $\Gamma $ so that $g \cdot g' = f_{g^{-1}}(g') = g'g^{-1}$ for all $g' \in G$ and $G \hookrightarrow \mathrm {Aut}(\Gamma )$ by identifying g with $f_{g^{-1}}$ . In addition, via this identification, G acts transitively on $\Gamma $ as a subgroup of graph automorphisms. In particular, every Cayley graph is transitive.
2.6 Partition functions
Given a graph $\Gamma = (V,E)$ , let us consider $\unicode{x3bb} : V \to \mathbb {R}_{>0}$ , an activity function. We call the pair $(\Gamma ,\unicode{x3bb} )$ a hardcore model. We will say that a hardcore model $(\Gamma ,\unicode{x3bb} )$ is finite if $\Gamma $ is finite. If $U \subseteq V$ is a finite subset, a fact that we denote by $U \Subset V$ , and $x \in X(\Gamma )$ is an independent set, we define the $\unicode{x3bb} $ -weight of x on U as
and the $(\Gamma ,U,\unicode{x3bb} )$ -partition function as
where $X(\Gamma ,U) := \{x \in X(\Gamma ): x(v) = 0 \text { for all } v \notin U\}$ is the finite set corresponding to the subset of independent sets of $\Gamma $ supported on U. It is easy to check that there is an identification between $X(\Gamma ,U)$ and $X(\Gamma [U])$ . Then, the quantity $Z_\Gamma (U,\unicode{x3bb} )$ corresponds to the summation of independent sets of $\Gamma [U]$ weighted by $\unicode{x3bb} $ . In the special case $\unicode{x3bb} \equiv 1$ , we have that $Z_\Gamma (U,1) = \lvert X(\Gamma ,U) \rvert = \lvert X(\Gamma [U]) \rvert $ , that is, the partition function is exactly the number of independent sets supported on U. If $(\Gamma ,\unicode{x3bb} )$ is finite, we will simply write $Z_\Gamma (\unicode{x3bb} )$ instead of $Z_\Gamma (V,\unicode{x3bb} )$ .
Remark 2.1. Notice that if $(v,v) \in E$ or $\unicode{x3bb} (v) = 0$ , then $Z_\Gamma (U,\unicode{x3bb} ) = Z_{\Gamma }(U \setminus \{v\},\unicode{x3bb} )$ ; due to this fact, we usually ask $\unicode{x3bb} $ to be strictly positive and that $\Gamma $ is loopless.
3 Free energy
Now, suppose that we have an increasing sequence $\{U_n\}_n$ of finite subsets of vertices exhausting $\Gamma $ , that is, $U_n \subseteq U_{n+1}$ and $\bigcup _n U_n = V$ . Tentatively, we would like to define the exponential growth rate of $Z_\Gamma (V_n,\unicode{x3bb} )$ as
To guarantee the existence of this limit, we will provide a self-contained argument based on the particular properties of the hardcore model and amenability. The reader that is familiar with this kind of argument may skim over the next part and go then to §4.
3.1 Amenability
Let
be the set of finite non-empty subsets of G. Given $g \in G$ and $K,F \subseteq G$ , we denote $Fg = \{hg: h {\kern-1pt}\in{\kern-1pt} F\}$ , $gF {\kern-1pt}={\kern-1pt} \{g h: h {\kern-1pt}\in{\kern-1pt} F\}$ , $F^{-1} {\kern-1pt}:={\kern-1pt} \{g^{-1}: g {\kern-1pt}\in{\kern-1pt} F\}$ , and $KF {\kern-1pt}={\kern-1pt} \{hg: h {\kern-1pt}\in{\kern-1pt} K, g {\kern-1pt}\in{\kern-1pt} F\}$ .
We say that $\{F_n\}_n \subseteq \mathcal {F}(G)$ is a right Følner sequence if
where $\triangle $ denotes the symmetric difference. Similarly, $\{F_n\}_n$ is a left Følner sequence if
and $\{F_n\}_n$ is a two-sided Følner sequence if it is both a left and a right Følner sequence. The group G is said to be amenable if it has a (right or left) Følner sequence. Notice that $\{F_n\}_n$ is left Følner if and only if $\{F_n^{-1}\}_n$ is right Følner. A Følner sequence $\{F_n\}_n$ is a Følner exhaustion if in addition $F_n \subseteq F_{n+1}$ and $\bigcup _n F_n = G$ . Every countable amenable group has a two-sided Følner exhaustion (see [Reference Kerr and Li26, Theorem 4.10]).
Every virtually amenable group is amenable. Moreover, the class of amenable groups contains all finite and all abelian groups, and it is closed under the operations of taking subgroups and forming quotients, extensions, and directed unions (see [Reference Ceccherini-Silberstein and Coornaert12]).
3.2 Growth rate of independent sets
Given $\emptyset \neq U \Subset V$ , define $\varphi _U: \mathcal {F}(G) \to \mathbb {R}$ as
From now on, we will assume that $\unicode{x3bb} : V \to \mathbb {R}_{>0}$ is G-invariant, this is to say,
In other words, $\unicode{x3bb} $ is constant along the G-orbits, so it achieves at most $\lvert \Gamma /G \rvert $ different values. We denote by $\unicode{x3bb} _+$ and $\unicode{x3bb} _-$ the maximum and minimum among these values, respectively.
Now, let W be an abstract set, M a finite subset of W, and $k \in \mathbb {N}$ . We will say that a finite collection $\mathcal {K}$ of non-empty finite subsets of W, with possible repetitions, is a k-cover of M if , where denotes the indicator function of a set $A \subseteq W$ . The following lemma is due to Downarowicz, Frej, and Romagnoli.
Lemma 3.1. [Reference Downarowicz, Frej, Romagnoli, Kolyada, Möller, Moree and Ward14]
Let Y be a subset of $A^{n}$ , where A is a finite set and $n \in \mathbb {N}$ . Let $\mathcal {K}$ be a k-cover of the set of coordinates $M = \{1,\ldots , n\}$ . For $K \in \mathcal {K}$ , let $Y_{K} = \{y_K: y \in Y\}$ , where $y_K$ is the restriction of y to K. Then,
Given $\varphi : \mathcal {F}(G) \to \mathbb {R}$ , we will say that $\varphi $ satisfies Shearer’s inequality if
for all $F \in \mathcal {F}(G)$ and for all k-cover $\mathcal {K}$ of F with $K \subseteq F$ for all $K \in \mathcal {K}$ . We have the following theorem.
Theorem 3.2. [Reference Kerr and Li26, Theorem 4.48]
Given a countable amenable group G, suppose that $\varphi : \mathcal {F}(G) \to \mathbb {R}$ satisfies Shearer’s inequality and $\varphi (Fg) = \varphi (F)$ for all $F \in \mathcal {F}(G)$ and $g \in G$ . Then,
for any Følner sequence $\{F_n\}_n$ .
Considering the two previous results, we obtain the next lemma.
Lemma 3.3. Given a fundamental domain $U_0$ of $G \curvearrowright \Gamma $ and $\unicode{x3bb} : V \to \mathbb {Q}_{> 0}$ such that $\unicode{x3bb} (v) = {p_v}/{q_v}$ with $p_v, q_v \in \mathbb {N}$ for all $v \in V$ , we have that, for any Følner sequence $\{F_n\}_n$ ,
where $\varphi : \mathcal {F}(G) \to \mathbb {R}$ is given by $\varphi (F) = \log Z_\Gamma (FU_0, \unicode{x3bb} ) + \lvert F \rvert \sum _{v \in U_0} \log q_v$ .
Proof. Given $F \in \mathcal {F}(G)$ and $k \in \mathbb {N}$ , let $\mathcal {K}$ be a k-cover of F with $K \subseteq F$ for all $K \in \mathcal {K}$ . Notice that
Consider $q := \max _v q_v$ , $p := \max _v p_v$ , $A := \{-q,\ldots ,-1\} \cup \{1,\ldots ,p\}$ , and
Notice that
Therefore, by Lemma 3.1, and noticing that $\lvert Y_{KU_0} \rvert = \prod _{v \in KU_0} q_v \cdot Z_\Gamma (KU_0,\unicode{x3bb} )$ , we have that
where we use that $\{KU_0: K \in \mathcal {K}\kern1.2pt\}$ is a k-cover of $FU_0$ . Therefore, by G-invariance of $\unicode{x3bb} $ ,
so $\varphi $ satisfies Shearer’s inequality. However, by G-invariance of $X(\Gamma )$ and $\unicode{x3bb} $ , it follows that $\varphi (Fg) = \varphi (F)$ for all $F \in \mathcal {F}(G)$ and $g \in G$ . Therefore, by Theorem 3.2, we conclude.
Proposition 3.4. Given a fundamental domain $U_0$ of $G \curvearrowright \Gamma $ , we have that
for any Følner sequence $\{F_n\}_n$ .
Proof. First, suppose that $\unicode{x3bb} $ only takes rational values, that is, $\unicode{x3bb} {\kern-1.2pt}:{\kern-1.2pt} V {\kern-1.2pt}\to{\kern-1.2pt} \mathbb {Q}_{>0}$ so that $\unicode{x3bb} (v) = {p_v}/{q_v}$ for all $v \in V$ . By Lemma 3.3, for $\varphi (F) = \log Z_\Gamma (FU_0, \unicode{x3bb} ) + \lvert F \rvert \sum _{v \in U_0} q_v$ , we have that
and, after canceling out $\sum _{v \in U_0} q_v$ , we obtain that
Now, given a general $\unicode{x3bb} $ , we can always approximate it by some G-invariant $\tilde {\unicode{x3bb} }{\kern-1.2pt}:{\kern-1.2pt} V {\kern-1.2pt}\to{\kern-1.2pt} \mathbb {Q}_{>0}$ arbitrarily close in the supremum norm. Given $\epsilon> 0$ , pick $\tilde {\unicode{x3bb} }$ so that $\tilde {\unicode{x3bb} }(v) \leq \unicode{x3bb} (v) \leq (1+\epsilon )\tilde {\unicode{x3bb} }(v)$ for every v. Then,
so,
Therefore,
and since $\epsilon $ was arbitrary, we conclude.
To fully characterize $\lim _n ({\log Z_\Gamma (U_n, \unicode{x3bb} )}/{\lvert U_n \rvert })$ , we have the following lemma.
Lemma 3.5. Let $\{F_n\}_n$ be a Følner sequence and $U_0$ a fundamental domain. Then, for any Følner sequence $\{F_n\}_n$ ,
Proof. First, pick $v \in U_0$ . Since $\mathrm {Stab}_G(v)$ is finite and $\{F_n\}_n$ is a Følner sequence, we have that $\lim _n {\lvert F_n \mathrm {Stab}_G(v) \rvert }/{\lvert F_n \rvert } = 1$ . However, $F_n \mathrm {Stab}_G(v) v = F_n v$ and for each $v' \in F_n v$ , there exist exactly $\lvert \mathrm {Stab}_G(v) \rvert $ different elements $g \in F_n \mathrm {Stab}_G(v)$ such that $g v = v'$ . In other words,
so,
Therefore,
Now, given a fundamental domain $U_0$ , define
which, by Proposition 3.4 and Lemma 3.5, is equal to
for any Følner sequence $\{F_n\}_n$ and, in particular, for any Følner exhaustion. Notice that, since $GU_0 = V$ , the sequence $\{U_n\}_n$ defined as $U_n = F_nU_0$ is an exhaustion of V in the sense for which we were looking. Now we will see that $f_{G}(\Gamma ,U_0,\unicode{x3bb} )$ is independent of $U_0$ .
Proposition 3.6. Given two fundamental domains $U_0$ and $U_0'$ of $G \curvearrowright \Gamma $ , we have that
Proof. Since $V = GU_0 = GU_0'$ , there must exist $K,K' \in \mathcal {F}(G)$ such that $U_0' \subseteq KU_0$ and $U_0 \subseteq K'U_0'$ . Then, for every $F \in \mathcal {F}(G)$ ,
Therefore, $\lvert FU_0 \triangle FU_0 \rvert \leq \lvert FK' \setminus F \rvert \lvert U_0' \rvert + \lvert FK \setminus F \rvert \lvert U_0 \rvert $ . Now, notice that for $U, U' \Subset V$ , we always have that:
-
(1) $Z_\Gamma (U \cup U',\unicode{x3bb} ) \leq Z_\Gamma (U,\unicode{x3bb} ) \cdot Z_\Gamma (U',\unicode{x3bb} )$ , provided $U \cap U' = \emptyset $ ;
-
(2) $Z_\Gamma (U,\unicode{x3bb} ) \leq Z_\Gamma (U',\unicode{x3bb} )$ , provided $U \subseteq U'$ ; and
-
(3) $Z_\Gamma (U,\unicode{x3bb} ) \leq (2\max \{1,\unicode{x3bb} _+\})^{\lvert U \rvert }$ ,
so
Finally, since $\lvert U_0 \rvert = \lvert U_0' \rvert $ and $\lvert FU_0 \rvert = \lvert F \rvert \lvert U_0 \rvert $ , it follows by amenability that
and by symmetry of the argument, we conclude.
Then, we can consistently define the Gibbs $(\Gamma ,\unicode{x3bb} )$ -free energy according to G as
where $U_0$ is an arbitrary fundamental domain of $G \curvearrowright \Gamma $ . In addition, it is easy to see that if $G_1$ and $G_2$ act almost transitively on $\Gamma $ , and the $G_1$ -orbits and $G_2$ -orbits coincide, that is, $G_1 v = G_2 v$ for all $v \in V$ , then
In particular, we have that $f_G(\Gamma ,\unicode{x3bb} )$ is equal for all G acting transitively on $\Gamma $ . Then, we can define the Gibbs $(\Gamma ,\unicode{x3bb} )$ -free energy as
which is a quantity that only depends on the graph $\Gamma $ and the activity function $\unicode{x3bb} $ , and satisfies that $f(\Gamma ,\unicode{x3bb} ) = f_G(\Gamma ,\unicode{x3bb} )$ for any $G \leq \mathrm {Aut}(\Gamma )$ acting transitively on $\Gamma $ .
Remark 3.7. In the almost transitive case, $f_G(\Gamma ,\unicode{x3bb} )$ does not necessarily coincide with $f(\Gamma ,\unicode{x3bb} )$ for G acting almost transitively: consider the graph $\Gamma $ obtained by taking the disjoint union of $\Gamma _1 = \mathrm {Cay}(\mathbb {Z},\emptyset )$ and $\Gamma _2 = \mathrm {Cay}(\mathbb {Z},\{1,-1\})$ , and the constant activity function $\unicode{x3bb} \equiv 1$ . Then, $f_{\mathbb {Z}}(\Gamma _1,1) = \log 2$ and $f_{\mathbb {Z}}(\Gamma _2,1) = \log (({1+\sqrt {5}})/{2})$ , so
The value of $f_{\mathbb {Z}}(\Gamma _2,1)$ corresponds to the topological entropy of the golden mean shift (see [Reference Lind and Marcus27, Example 4.1.4] and §9).
The main theme of this paper will be to explore our ability to approximate $f_G(\Gamma ,\unicode{x3bb} )$ . From now, and without much loss of generality, we will assume that $G \curvearrowright \Gamma $ is free (see §9.7 for a reduction of the almost free case to the free case).
4 Gibbs measures
Given a graph $\Gamma = (V,E)$ , consider the set $\{0,1\}^{V}$ endowed with the product topology and the set $X(\Gamma )$ , with the subspace topology. The set of independent sets $X(\Gamma )$ is a compact and metrizable space. A base for the topology is given by the cylinder sets
for $U \Subset V$ and $x \in X(\Gamma )$ , where $x_U$ denotes the restriction of x from V to U. If U is a singleton $\{v\}$ , we will omit the brackets and simply write $x_v$ and the same convention will hold in analogous instances. Given $W \subseteq V$ , we denote by $\mathcal {B}_W$ the smallest $\sigma $ -algebra generated by
and by $\mathcal {B}_\Gamma $ the Borel $\sigma $ -algebra, which corresponds to $\mathcal {B}_{V}$ .
Let $\mathcal {M}(X(\Gamma ))$ be the set of Borel probability measures $\mathbb {P}$ on $X(\Gamma )$ . We say that $\mathbb {P}$ is G-invariant if $\mathbb {P}(A) = \mathbb {P}(g \cdot A)$ for all $A \in \mathcal {B}_\Gamma $ and $g \in G$ , and G-ergodic if $g \cdot A = A$ for all $g \in G$ implies that $\mathbb {P}(A) \in \{0,1\}$ . We will denote by $\mathcal {M}_G(X(\Gamma ))$ and $\mathcal {M}_G^{\mathrm {erg}}(X(\Gamma ))$ the set of G-invariant and the subset of G-invariant measures that are G-ergodic, respectively.
For $\mathbb {P} \in \mathcal {M}(X(\Gamma ))$ , define the support of $\mathbb {P}$ as
Given $\emptyset \neq U \Subset V$ and $y \in X(\Gamma )$ , we define $\pi ^y_U$ to be the probability distribution on $X(\Gamma ,U)$ given by
where and $Z^y_\Gamma (U,\unicode{x3bb} ) = \sum _x \mathrm {w}^y_\unicode{x3bb} (x,U)$ . In other words, to each independent set x supported on U, we associate a probability proportional to its $\unicode{x3bb} $ -weight over U, $\prod _{v \in U} \unicode{x3bb} (v)^{x(v)}$ , provided $x_U$ is compatible with $y_{U^{\mathrm { c}}}$ , in the sense that the element $z \in \{0,1\}^{V}$ such that $z_U = x_U$ and $z_{U^{\mathrm { c}}} = y_{U^{\mathrm { c}}}$ is an independent set.
Now, given an activity function $\unicode{x3bb} : V \to \mathbb {R}_{>0}$ , consider the hardcore model $(\Gamma , \unicode{x3bb} )$ and the collection $\pi _{\Gamma ,\unicode{x3bb} } = \{\pi ^y_U: U \Subset V, y \in X(\Gamma )\}$ . We call $\pi _{\Gamma ,\unicode{x3bb} }$ the Gibbs $(\Gamma ,\unicode{x3bb} )$ -specification. A measure $\mathbb {P} \in \mathcal {M}(X(\Gamma ))$ is called a Gibbs measure (for $(\Gamma ,\unicode{x3bb} )$ ) if for all $U \Subset V$ , $U' \subseteq U$ , and $x \in X(\Gamma )$ ,
where $\pi ^y_U([x_U'])$ denotes the marginalization
and for $A \in \mathcal {B}_\Gamma $ . We denote by $\mathcal {M}_{\mathrm {Gibbs}}(\Gamma ,\unicode{x3bb} )$ the set of Gibbs measures for $(\Gamma ,\unicode{x3bb} )$ .
An important question in statistical physics is whether the set of Gibbs measures is empty or not, and if not, whether there is a unique or multiple Gibbs measures [Reference Georgii17].
4.1 The locally finite case
The model described in [Reference Georgii17, Example 4.16] can be understood as an attempt to formalize the idea of a system where there is a single particle $1$ (uniformly distributed) or none, that is, $0$ everywhere. There, it is proven that this model cannot be represented as a Gibbs measure. This example can be also viewed as a hardcore model in a countable graph that is complete (that is, there is an edge between any pair of different vertices) and, in particular, in a non-locally finite graph. In other words, there exist examples of non-locally finite graphs $\Gamma $ such that the $(\Gamma ,\unicode{x3bb} )$ -specification $\pi _{\Gamma ,\unicode{x3bb} }$ has no Gibbs measure.
From now on, we will always assume that $\Gamma $ is locally finite. In this case, the existence of Gibbs measures is guaranteed (see [Reference Brightwell and Winkler10, Reference Dobrushin13]) and, moreover, every Gibbs measure must be a Markov random field that is fully supported.
Indeed, it can be checked that $\pi _{\Gamma ,\unicode{x3bb} }$ is an example of a Markovian specification (see [Reference Georgii17, Example 8.24]). In this case, any Gibbs measure $\mathbb {P} \in \mathcal {M}_{\mathrm {Gibbs}}(\Gamma ,\unicode{x3bb} )$ satisfies the following local Markov property:
for any $U \Subset V$ and $x \in X(\Gamma )$ . In other words, $\mathbb {P}$ is a Markov random field, so any event supported on a finite set conditioned to a specific value on its boundary is independent of events supported on the complement.
In addition, it can be checked that any Gibbs measure $\mathbb {P}$ must be fully supported, that is, $\mathrm {supp}(\mathbb {P}) = X(\Gamma )$ . Indeed, it suffices to check that $X(\Gamma ) \subseteq \mathrm {supp}(\mathbb {P})$ ; the other direction follows directly from the definition of $\pi _{\Gamma ,\unicode{x3bb} }$ and Gibbs measures. Now, given $x \in X(\Gamma )$ and $U \Subset V$ , we would like to check that $\mathbb {P}([x_U])> 0$ . To prove this, observe that given $x \in X(\Gamma )$ , we have that $z \in \{0,1\}^{V}$ defined as $z_U = x_U$ , $z_{\partial U} \equiv 0$ , and $z_{W^c} = y_{W^c}$ always belongs to $X(\Gamma )$ for any $y \in X(\Gamma )$ , where $W = U \cup \partial U$ . In particular, $\pi ^y_{W}(z)> 0$ for any $y \in X(\Gamma )$ . Then, considering that $\partial (W^c)$ is finite,
since $\mathbb {P}$ is a probability measure and there must exist $y^* \in X(\Gamma )$ such that $\mathbb {P}([y^*_{\partial W}])> 0$ . In other words, $X(\Gamma )$ satisfies the property (D*) introduced in [Reference Ruelle41, 1.14 Remark], which guarantees full support.
4.2 Spatial mixing and uniqueness
Given a Gibbs $(\Gamma ,\unicode{x3bb} )$ -specification $\pi _{\Gamma ,\unicode{x3bb} }$ , we define two spatial mixing properties fundamental to this work.
Definition 4.1. We say that a hardcore model $(\Gamma ,\unicode{x3bb} )$ exhibits strong spatial mixing (SSM) if there exists a decay rate function $\delta : \mathbb {N} \to \mathbb {R}_{\geq 0}$ such that $\lim _{\ell \to \infty } \delta (\ell ) = 0$ and for all $U \Subset V$ , $v \in U$ , and $y,z \in X(\Gamma )$ ,
where $[0^v]$ denotes the event that the vertex v takes the value $0$ and
This definition is equivalent (see [Reference Marcus and Pavlov35, Lemma 2.3]) to the—a priori—stronger following property: for all $U' \subseteq U \Subset V$ and $x,y,z \in X(\Gamma )$ ,
Similarly, we say that $(\Gamma ,\unicode{x3bb} )$ exhibits weak spatial mixing (WSM) if for all $U' \subseteq U \Subset V$ and $x,y,z \in X(\Gamma )$ ,
Clearly, SSM implies WSM. Moreover, it is well known that, in this context, WSM (and therefore, SSM) implies uniqueness of Gibbs measures [Reference Weitz54]. In other words, $\mathcal {M}_{\mathrm {Gibbs}}(\Gamma ,\unicode{x3bb} ) = \{\mathbb {P}_{\Gamma ,\unicode{x3bb} }\}$ , where $\mathbb {P}_{\Gamma ,\unicode{x3bb} }$ denotes the unique Gibbs measure for $(\Gamma ,\unicode{x3bb} )$ . In this case, $\mathbb {P}_{\Gamma ,\unicode{x3bb} }$ is always $\mathrm {Aut}(\Gamma )$ -invariant.
We say that $(\Gamma ,\unicode{x3bb} )$ exhibits exponential SSM (respectively exponential WSM) if there exist constants $C,\alpha> 0$ such that $\pi _{\Gamma ,\unicode{x3bb} }$ exhibits SSM (respectively WSM) with decay rate function $\delta (n) = C \cdot \exp (-\alpha \cdot n)$ .
Given $U \subseteq V$ , we denote by $\Gamma \setminus U$ the subgraph induced by $V \setminus U$ , that is, $\Gamma [V \setminus U]$ . We have the following result due to Gamarnik and Katz.
Proposition 4.1. [Reference Gamarnik and Katz16, Proposition 1]
If a hardcore model $(\Gamma ,\unicode{x3bb} )$ satisfies SSM, then so does the hardcore model $(\Gamma ',\unicode{x3bb} )$ for any subgraph $\Gamma '$ of $\Gamma $ . The same assertion applies to exponential SSM. Moreover, for every $U \subseteq V$ and $v \in V \setminus U$ , the following identity holds:
where $\mathbb {P}_{\Gamma ,\unicode{x3bb} }$ and $\mathbb {P}_{\Gamma \setminus U,\unicode{x3bb} }$ are the unique Gibbs measures for $(\Gamma ,\unicode{x3bb} )$ and $(\Gamma \setminus U,\unicode{x3bb} )$ , respectively, and $[0^U]$ denotes the event that all the vertices in U take the value $0$ . In particular, $\mathbb {P}_{\Gamma ,\unicode{x3bb} }([0^v] \vert [0^U])$ is always well defined, even if U is infinite.
Remark 4.2. Notice that any event of the form $[x_U]$ can be translated into an event of the form $[0^{U' }]$ for a suitable set $U'$ : it suffices to define $U' = U \cup \partial \{v \in U: x_U(v) = 1\}$ since, deterministically, every neighbor of a vertex colored $1$ must be $0$ , so Proposition 4.1 still holds for more general events. We also remark that in [Reference Gamarnik and Katz16], it is assumed that $\unicode{x3bb} $ is a constant function. Here we drop this assumption, but it is direct to check that the same proof of [Reference Gamarnik and Katz16, Proposition 1] also applies to the more general non-constant case.
4.3 Families of hardcore models
We will denote by $\mathcal {H}$ the family of hardcore models $(\Gamma , \unicode{x3bb} )$ such that $\Gamma $ is a countable locally finite graph and $\unicode{x3bb} $ is any activity function $\unicode{x3bb} : V(\Gamma ) \to \mathbb {R}_{>0}$ .
Given a countable group G, we will denote by $\mathcal {H}_G$ the set of hardcore models $(\Gamma ,\unicode{x3bb} )$ in $\mathcal {H}$ for which G is isomorphic to some subgroup of $\mathrm {Aut}(\Gamma )$ such that $G \curvearrowright \Gamma $ is free and almost transitive and $\unicode{x3bb} : V(\Gamma ) \to \mathbb {R}_{>0}$ is a G-invariant activity function.
Given a positive integer $\Delta $ , we will denote by $\mathcal {H}^\Delta $ the set of hardcore models $(\Gamma ,\unicode{x3bb} )$ in $\mathcal {H}$ such that $\Delta (\Gamma ) \leq \Delta $ . Notice that any hardcore model defined on the $\Delta $ -regular (infinite) tree $\mathbb {T}_\Delta $ belongs to $\mathcal {H}^\Delta $ .
Given $\unicode{x3bb} _0> 0$ , we will denote by $\mathcal {H}(\unicode{x3bb} _0)$ the family of hardcore models $(\Gamma ,\unicode{x3bb} )$ in $\mathcal {H}$ such that $\unicode{x3bb} _+ \leq \unicode{x3bb} _0$ .
We will also combine the notation for these families in the natural way; for example, $\mathcal {H}_G^\Delta (\unicode{x3bb} _0)$ will denote the set of hardcore models $(\Gamma ,\unicode{x3bb} )$ in $\mathcal {H}$ such that $G \curvearrowright \Gamma $ is free and almost transitive, $\unicode{x3bb} $ is G-invariant, $\Delta (\Gamma ) \leq \Delta $ , and $\unicode{x3bb} _+ \leq \unicode{x3bb} _0$ .
5 Trees
Given a graph $\Gamma $ , a trail w in $\Gamma $ is a finite sequence $w = (v_1,\ldots ,v_n)$ of vertices such that consecutive vertices are adjacent in $\Gamma $ and the edges $(v_i,v_{i+1})$ involved are not repeated. For a fixed vertex $v \in V(\Gamma )$ , the tree of self-avoiding walks starting from v, denoted by $T_{\mathrm {SAW}}(\Gamma ,v)$ , is defined as follows.
-
(1) Consider the set $W_0$ of trails starting from v that repeat no vertex and the set $W_1$ of trails that repeat a single vertex exactly once and then stop (that is, the set of non-backtracking walks that end immediately after performing a cycle). We define $T_{\mathrm {SAW}}(\Gamma ,v)$ to be a rooted tree with root $\rho = (v)$ such that the set of vertices $V(T_{\mathrm {SAW}}(\Gamma ,v))$ is $W_0 \cup W_1$ and the set of (undirected) edges $E(T_{\mathrm {SAW}}(\Gamma ,v))$ corresponds to all the pairs $(w,w')$ such that $w'$ is a one-vertex extension of w or vice versa. In simple words, $T_{\mathrm {SAW}}(\Gamma ,v)$ is a rooted tree that represents all self-avoiding walks in $\Gamma $ that start from v. It is easy to check that the set of leaves of $T_{\mathrm {SAW}}(\Gamma ,v)$ contains $W_1$ , but they are not necessarily equal (e.g., see vertex b in Figure 2).
-
(2) For $u \in V(\Gamma )$ , consider an arbitrary ordering $\partial \{u\} = \{u_1, \ldots , u_d\}$ of its neighbors. Given $w \in W_1$ , we can represent this walk as a sequence
$$ \begin{align*}w = (v,\ldots, u,u_i,\ldots,u_j,u),\end{align*} $$with $u_i,u_j \in \partial \{u\}$ . Notice that $i \neq j$ , since we are not repeating edges. Considering this, we condition the ‘terminal’ trail w to be $1$ (occupied) if $i < j$ and to be $0$ (unoccupied) if $i> j$ , inducing the corresponding effect of this conditioning in the graph (that is, removing the vertex and its neighbors or just removing the vertex, respectively).
Given a hardcore model $(\Gamma ,\unicode{x3bb} )$ , a vertex $v \in V(\Gamma )$ , a subset $U \subseteq V(\Gamma )$ , and an independent set $x \in X(\Gamma )$ , we are interested in computing the marginal probability that v is unoccupied in $\Gamma $ given the partial configuration $x_U$ , that is, $\mathbb {P}_{\Gamma ,\unicode{x3bb} }([0^v] \vert [x_U])$ . Notice that if $(\Gamma ,\unicode{x3bb} )$ satisfies SSM (which includes the particular but relevant case of $\Gamma $ being finite), then this probability is always well defined due to Proposition 4.1, even if U is infinite.
To understand better $\mathbb {P}_{\Gamma ,\unicode{x3bb} }([0^v] \vert [x_U])$ , we consider $(T_{\mathrm {SAW}}(\Gamma ,v),\overline {\unicode{x3bb} })$ to be the hardcore model where $\overline {\unicode{x3bb} }(w) = \unicode{x3bb} (u)$ for every trail w ending in u. In this context, a condition $x_U$ in $(\Gamma ,\unicode{x3bb} )$ is translated into the condition $\overline {x_U}$ in $T_{\mathrm {SAW}}(\Gamma ,v)$ , whose support is the set $W(U)$ of trails w that end in u for some $u \in U$ , and $\overline {x}(w) = x(u)$ for all these w. We have the following result from [Reference Weitz55], that we adapt to the more general non-constant $\unicode{x3bb} $ case and we include its proof for completeness.
Theorem 5.1. [Reference Weitz55, Theorem 3.1]
For every finite hardcore model $(\Gamma ,\unicode{x3bb} )$ , every $v \in V(\Gamma )$ , and $U \subseteq V(\Gamma )$ ,
Proof. Instead of probabilities, we work with the ratios
where if $v \in U$ and $x_U(v)$ is equal to $1$ or $0$ , we let $R_{\Gamma ,\unicode{x3bb} }(v,x_U)$ be $\infty $ or $0$ , respectively. Notice that
Given a finite tree T rooted at $\rho $ , let us denote by $\{\rho _1,\ldots ,\rho _d\}$ the set of neighbors $\partial \{\rho \}$ of $\rho $ and by $T_i$ , for $i=1,\ldots ,d$ , the corresponding subtrees starting from $\rho _i$ , that is, $V(T) = \{\rho \} \cup V(T_1) \cup \cdots \cup V(T_d)$ . If we have a condition $x_U$ on U, we define $U_i = U \cap V(T_i)$ and $x_{U_i} = (x_{U})\vert _{U_i}$ . Considering this, we have that
where
Notice that this gives us a linear recursive procedure for computing $R_{T,\unicode{x3bb} }(\rho , x_U)$ , and therefore $\mathbb {P}_{T,\unicode{x3bb} }([0^\rho ] \vert [x_U])$ , with base cases: $R_{T,\unicode{x3bb} }(\rho , x_U) = 0 \text { or } +\infty $ if $\rho $ is fixed, and $R_{T,\unicode{x3bb} }(\rho , x_U) = \unicode{x3bb} (\rho )$ if $\rho $ is free and isolated.
Now, consider an arbitrary hardcore model $(\Gamma ,\unicode{x3bb} )$ and $v \in V(\Gamma )$ with neighbors $\partial \{v\} = \{u_1,\ldots ,u_d\}$ . We consider the auxiliary hardcore model $(\Gamma ',\unicode{x3bb} ')$ , where:
-
• $V(\Gamma ') = V(\Gamma ) \backslash \{v\} \cup \{v_1,\ldots ,v_d\}$ ;
-
• $E(\Gamma ') = E(\Gamma ) \backslash \{(v,u_i)\}_{i=1,\ldots ,d} \cup \{(v_i,u_i)\}_{i=1,\ldots ,d}$ ;
-
• $\unicode{x3bb} '(v_i) = \unicode{x3bb} (v)^{1/d}$ for $i=1,\ldots ,d$ , and $\unicode{x3bb} '(u) = \unicode{x3bb} (u)$ otherwise.
Notice that
where $z_i = 0^{\{v_1,\ldots ,v_{i-1}\}}1^{\{v_{i+1}, \ldots , v_d\}}$ and $x_Uz_i$ is the concatenation of $x_U$ and $z_i$ . Now, since $v_i$ is connected only to $u_i$ , notice that
Therefore,
Notice that the previous recursion can increase the original number of vertices, but the number of free vertices always decreases, so the recursion ends. Then, we have that:
-
(1) $R_{T,\unicode{x3bb} }(v, x_U) = \unicode{x3bb} (\rho ) \cdot f(R_{T_1,\unicode{x3bb} }(\rho _1, x_{U_1}),\ldots ,R_{T_d,\unicode{x3bb} }(\rho _d, x_{U_d}))$ ; and
-
(2) $R_{\Gamma ,\unicode{x3bb} }(v, x_U) = \unicode{x3bb} (v) \cdot f(R_{\Gamma ' \backslash \{v_1\},\unicode{x3bb} '}(u_1,x_U\tau _1),\ldots ,R_{\Gamma ' \backslash \{v_d\},\unicode{x3bb} '}(u_d,x_U\tau _d))$ ,
where $f(r_1,\ldots ,r_d) = \prod _{i=1}^{d}({1}/{(1+r_i)})$ . Now we proceed by induction in the number of free vertices. We can consider the base case where there are no free vertices (besides v) and the theorem is trivial. Then, if we know that the theorem is true when we have n free vertices, we prove it for $n+1$ . Notice that if $R_{\Gamma ',\unicode{x3bb} '}(v,x_U)$ involves $n+1$ free vertices, then $R_{\Gamma ' \setminus \{v\},\unicode{x3bb} '}(v_i,x_Uz_i)$ involves n free vertices, so by the induction hypothesis,
Then, noticing that the rooted subtree $(T_i,\rho _i)$ and the condition $\overline {x_{U}z_i}$ give exactly the tree of self-avoiding walks of $\Gamma ' \backslash \{v_i\}$ starting from $u_i$ under the condition $x_Uz_i$ , we are done.
Remark 5.2. The recursions presented in the proof of Theorem 5.1 give us a recursive procedure to compute the marginal probability of the root $\rho $ of a tree T being occupied which requires linear time with respect to the size of the tree. However, if $\Gamma $ is such that $\Delta (\Gamma ) \leq \Delta $ , then $T_{\mathrm {SAW}}(\Gamma ,v)$ is a subtree of $\mathbb {T}_\Delta $ and its size of $T_{\mathrm {SAW}}(\Gamma ,v)$ can be (at most) exponential in the size of $\Gamma $ . Since hardcore models are Markov random fields and we are interested in the sensitivity of the root $\rho $ associated to v, we only need to consider the graph obtained after pruning all the subtrees below $W(U)$ (see Figure 3).
Before stating the main results concerning hardcore models and strong spatial mixing, we will establish the following bounds.
Lemma 5.3. Given a finite hardcore model $(\Gamma ,V) \in \mathcal {H}^\Delta $ and $v \in V$ , we have that
and
Proof. Notice that, since a $1$ at v forces $0$ s in $\partial \{v\}$ ,
so, considering that $\mathbb {P}_{\Gamma ,\unicode{x3bb} }$ is a Markov random field and ${\unicode{x3bb} }/({1+\unicode{x3bb} })$ is increasing in $\unicode{x3bb}> 0$ , we obtain that
and
However, by Theorem 5.1, without loss of generality, we can suppose that $\Gamma $ is a tree rooted at v. Then, if $\Gamma _i$ denotes the ith subtree of $\Gamma $ rooted at $v_i \in \partial \{v\}$ ,
Therefore, since $\mathbb {P}_{\Gamma ,\unicode{x3bb} }([0^v]) = 1 - \mathbb {P}_{\Gamma ,\unicode{x3bb} }([1^v])$ , we have that
We define the critical activity function $\unicode{x3bb} _c: [2,+\infty ) \to (0,+\infty ]$ as
We have the following result.
Proposition 5.4. [Reference Kelly25]
For every $\Delta \in \mathbb {N}$ , the hardcore model $(\mathbb {T}_{\Delta }, \unicode{x3bb} _0)$ exhibits WSM if and only if $\unicode{x3bb} _0 \leq \unicode{x3bb} _c(\Delta )$ . If the inequality is strict, then $(\mathbb {T}_{\Delta }, \unicode{x3bb} _0)$ exhibits exponential WSM with a decay rate $\delta $ involving constants that depend on $\Delta $ and $\unicode{x3bb} _0$ .
We summarize, in the following theorem, the main results from [Reference Weitz55] that relate the correlation decay in $(\mathbb {T}_{\Delta }, \unicode{x3bb} _0)$ with the correlation decay in $\mathcal {H}^\Delta (\unicode{x3bb} _0)$ . Here again, as in Theorem 5.1, the results in [Reference Weitz55] are focused on the constant activity case. However, we can also adapt the results to the non-constant case by considering that the main tool used in [Reference Weitz55] to prove them is [Reference Weitz55, Theorem 4.1], which is based on hardcore models with non-constant activity functions.
Theorem 5.5. [Reference Weitz55, Theorems 2.3 and 2.4]
Fix $\Delta \in \mathbb {N}$ and $\unicode{x3bb} _0> 0$ . Then:
-
(1) if $(\mathbb {T}_\Delta ,\unicode{x3bb} _0)$ exhibits WSM with decay rate $\delta $ , then $(\mathbb {T}_\Delta ,\unicode{x3bb} _0)$ exhibits SSM with rate
$$ \begin{align*}\frac{(1+\unicode{x3bb}_0)(\unicode{x3bb}_0 + (1+\unicode{x3bb}_0)^{\Delta})}{\unicode{x3bb}_0}\delta;\end{align*} $$ -
(2) if $(\mathbb {T}_\Delta ,\unicode{x3bb} _0)$ exhibits SSM with decay rate $\delta $ , then $(\Gamma ,\unicode{x3bb} )$ exhibits SSM with rate $\delta $ for every $(\Gamma ,\unicode{x3bb} ) \in \mathcal {H}^\Delta (\unicode{x3bb} _0)$ .
Then, combining Proposition 5.4 and Theorem 5.5, we have that if $\unicode{x3bb} _0 \leq \unicode{x3bb} _{c}(\Delta )$ , then every hardcore model $(\Gamma ,\unicode{x3bb} ) \in \mathcal {H}^\Delta (\unicode{x3bb} _0)$ exhibits SSM with the same decay rate $\delta $ that would be exponential if the inequality is strict. In addition, observe that if $(\Gamma ,\unicode{x3bb} )$ is a hardcore model such that $(T_{\mathrm {SAW}}(\Gamma ,v),\overline {\unicode{x3bb} })$ exhibits SSM with decay rate $\delta $ for every $v \in V(\Gamma )$ , then $(\Gamma ,\unicode{x3bb} )$ exhibits SSM with decay rate $\delta $ as well. This follows from Theorem 5.1, since SSM is a property that depends on finitely supported events and the probabilities involved can be translated into probabilities defined on finite hardcore models which at the same time can be translated into events on finite subtrees of $T_{\mathrm {SAW}}(\Gamma ,v)$ . Considering this, we have the following theorem, which can be understood as a generalization of Theorem 5.1 to the infinite setting.
Theorem 5.6. Given a hardcore model $(\Gamma ,\unicode{x3bb} )$ and $v \in V(\Gamma )$ such that $(T_{\mathrm {SAW}}(\Gamma ,v),\overline {\unicode{x3bb} })$ exhibits SSM, then for every $x \in X(\Gamma )$ and $U \subseteq V(\Gamma )$ ,
Proof. Assume that $(T_{\mathrm {SAW}}(\Gamma ,v),\overline {\unicode{x3bb} })$ exhibits SSM with decay rate $\delta $ . Then, for every $\ell \in \mathbb {N}$ ,
and, similarly,
Therefore, since $\lim _{\ell \to \infty } \delta (\ell ) = 0$ ,
and, by the same argument,
Considering this, the Markov random field property, and Proposition 4.1, we have that
Notice that Theorem 5.6 requires that $(T_{\mathrm {SAW}}(\Gamma ,v),\overline {\unicode{x3bb} })$ exhibits SSM rather than the graph $(\Gamma ,\unicode{x3bb} )$ , since SSM on $T_{\mathrm {SAW}}(\Gamma ,v)$ may be a stronger condition than SSM on $\Gamma $ . A key fact is that if $(\mathbb {T}_\Delta , \unicode{x3bb} _0)$ exhibits SSM, then $(T, \unicode{x3bb} _0)$ exhibits SSM for every subtree T of $\mathbb {T}_\Delta $ . Then, since for every $\Gamma $ with $\Delta (\Gamma ) \leq \Delta $ we have that $T_{\mathrm {SAW}}(\Gamma ,v)$ is a subtree of $\mathbb {T}_\Delta $ , it follows that $(T_{\mathrm {SAW}}(\Gamma ,v),\overline {\unicode{x3bb} })$ , and therefore $(\Gamma ,\unicode{x3bb} _0)$ , exhibit SSM. Considering this, we have the following corollary.
Corollary 5.7. Fix $\Delta \in \mathbb {N}$ . Then, every $(\Gamma ,\unicode{x3bb} ) \in \mathcal {H}^\Delta (\unicode{x3bb} _c(\Delta ))$ exhibits SSM and for every $v \in V(\Gamma )$ , $x \in X(\Gamma $ ), and $U \subseteq V(\Gamma )$ ,
Since we are ultimately interested in studying the interplay between the SSM property on $T_{\mathrm {SAW}}(\Gamma ,v)$ and $\Gamma $ , we may wonder whether it is really necessary to have control over the full $\Delta $ -regular tree $\mathbb {T}_\Delta $ . In [Reference Sinclair, Srivastava, Štefankovič and Yin46], a refinement of this fact was proved by considering the connective constant of the graphs involved.
5.1 Connective constant
Given a graph $\Gamma $ , a vertex v, and an integer k, let $N_\Gamma (v,k)$ denote the number of self-avoiding walks in $\Gamma $ of length k starting from v. Following [Reference Sinclair, Srivastava, Štefankovič and Yin46], we consider the connective constant $\mu (\mathcal {G})$ of a family of finite graphs $\mathcal {G}$ . Here, $\mu (\mathcal {G})$ is defined as the infimum over all $\mu> 0$ for which there exist $a,c> 0$ such that for any $\Gamma \in \mathcal {G}$ and any $v \in V(\Gamma )$ , it holds that $\sum ^\ell _{k=1} N_\Gamma (v,k) \leq c\mu ^\ell $ for all $\ell \geq a\log \lvert V(\Gamma ) \rvert $ . This definition extends the more usual definition of connective constant for a single infinite almost transitive graph $\Gamma $ , which is given by
Indeed, if $\Gamma $ is almost transitive, then $\mu (\Gamma ) = \mu (\mathcal {G}(\Gamma ))$ , where $\mathcal {G}(\Gamma )$ denotes the family of finite subgraphs of $\Gamma $ . Notice that $\mu (\Gamma )$ exists due to Fekete’s lemma and that, if $\Gamma $ is connected, then $\mu (\Gamma ) = \lim _{\ell \to \infty } N_\Gamma (v,\ell )^{1/\ell }$ for arbitrary v. Roughly, the connective constant measures the growth rate of the number of self-avoiding walks according to their length or, equivalently, the branching of $T_{\mathrm {SAW}}(\Gamma ,v)$ . In general, it is not an easy task to compute $\mu (\Gamma )$ (e.g., see [Reference Duminil-Copin and Smirnov15]).
Considering this, we extend the definition of strong spatial mixing to families of graphs as follows: given a family of graphs $\mathcal {G}$ and a family of activity functions $\Lambda = \{\unicode{x3bb} ^\Gamma \}_{\Gamma \in \mathcal {G}}$ with $\unicode{x3bb} ^\Gamma : V(\Gamma ) \to \mathbb {R}_{>0}$ , we say that $(\mathcal {G}, \Lambda )$ satisfies strong spatial mixing if there exists a decay rate function $\delta : \mathbb {N} \to \mathbb {R}_{\geq 0}$ such that $\lim _{\ell \to \infty } \delta (\ell ) = 0$ and for all $\Gamma \in \mathcal {G}$ , for all $U \Subset V(\Gamma )$ , $v \in U$ , and $y,z \in X(\Gamma )$ ,
where $\pi ^y_{\Gamma , U}$ denotes the specification element corresponding to the hardcore model $(\Gamma , \unicode{x3bb} ^\Gamma )$ . We translate into this language the following result from [Reference Sinclair, Srivastava, Štefankovič and Yin46].
Theorem 5.8. [Reference Sinclair, Srivastava, Štefankovič and Yin46]
Let $\mathcal {G}$ be a family of almost transitive locally finite graphs and $\Lambda = \{\unicode{x3bb} ^{\Gamma }\}_{\Gamma \in \mathcal {G}}$ a set of activity functions such that
Then, $(\mathcal {G}, \Lambda )$ exhibits exponential SSM.
Notice that if a graph has maximum degree $\Delta $ , then $\mu (\Gamma ) \leq \Delta -1$ . In addition, observe that $N_\Gamma (v,\ell ) = N_{T_{\mathrm {SAW}}(\Gamma ,v)}(\rho ,\ell )$ . We have the following corollary.
Corollary 5.9. If $(\Gamma ,\unicode{x3bb} )$ is a hardcore model such that
then $(T_{\mathrm {SAW}}(\Gamma ,v),\overline {\unicode{x3bb} })$ exhibits (exponential) SSM for every $v \in V(\Gamma )$ . In particular, $(\Gamma ,\unicode{x3bb} )$ exhibits (exponential) SSM and for every $v \in V(\Gamma )$ , $x \in X(\Gamma $ ), and $U \subseteq V(\Gamma )$ ,
6 Orders
We have already explored the main combinatorial and measure-theoretical tools that we require to establish the main results. In this section, we present some concepts of a more group-theoretical nature, namely, our ability to order a given group.
6.1 Orderable groups
Let $\prec $ be a strict total order on G. We say that $\prec $ is an invariant (right) order if, for all $h_1,h_2,g \in G$ ,
We call the pair $(G,\prec )$ a (linearly) ordered group. The associated algebraic past of an ordered group $(G,\prec )$ is the set $\Phi _\prec := \{g \in G: g \prec 1_G\}$ and it is a semigroup which satisfies that
Notice that $h \prec g \iff hg^{-1} \in \Phi _\prec $ , so $\Phi _\prec $ fully determines $\prec $ and vice versa.
The class of orderable groups contains all torsion-free abelian groups and it is closed under the operations of taking subgroups, and forming extensions, arbitrary direct products, and directed unions.
A group G is called virtually orderable (respectively ordered) if there exists an orderable (respectively ordered) subgroup $H \leq G$ of finite index $[G:H]$ . Notice that if $G \curvearrowright \Gamma $ is almost transitive and free with fundamental domain $U_0$ , then $H \curvearrowright \Gamma $ is also almost transitive and free with fundamental domain $KU_0$ , where $K \in \mathcal {F}(G)$ is any finite set of representatives. In particular, $\lvert \Gamma /H \rvert = \lvert \Gamma /G \rvert [G:H]$ . For this reason, since we are interested in almost transitive actions, there is no loss of generality if, given a virtually orderable group, we assume that it is just orderable: the free energies $f_G(\Gamma ,\unicode{x3bb} )$ and $f_H(\Gamma ,\unicode{x3bb} )$ will be equal and the only effect of passing to a finite-index subgroup will be that the size of the fundamental domain of the action is multiplied by a constant factor (that is, the index of the subgroup $[G:H]$ ). This last point is relevant, since the size of the fundamental domain will play a role later when measuring the computational complexity of some problems.
Given a finitely generated group G, a generating set S, and its corresponding Cayley graph $\Gamma = \mathrm {Cay}(G,S)$ , we define the volume growth function as $g_\Gamma (n) = \lvert B_\Gamma (1_G,n) \rvert $ . We say that G has polynomial growth if $g_\Gamma (n) \leq p(n)$ for some polynomial p. It is well known that groups with polynomial growth are amenable and a classic result due to Gromov asserts that they are virtually nilpotent [Reference Gromov19]. Without further detail, from Schreier’s lemma, it is also well known that finite index subgroups of finitely generated groups are also finitely generated [Reference Lyndon and Schupp32, Proposition 4.2] and finitely generated nilpotent groups have a torsion-free nilpotent subgroup with finite index [Reference Segal43, Proposition 2]. From this, and since torsion-free nilpotent groups are orderable [Reference Mura and Rhemtulla39, p. 37], it follows that any finitely generated group G with polynomial growth is amenable and virtually orderable. In particular, all our results that apply to amenable and virtually orderable groups will hold for groups of polynomial growth, but they will also hold in groups of super-polynomial—namely, exponential—growth. This includes solvable groups that are not virtually nilpotent [Reference Milnor38] and, more concretely, cases like the Baumslag–Solitar groups $\mathrm {BS}(1,n)$ that can also be ordered. However, not every amenable group is virtually orderable; for example, the direct sum of countably many non-trivial finite groups always results in a countable group that is amenable but not virtually orderable. To address these cases, we introduce a randomized generalization of invariant orders.
6.2 Random orders
Consider now the set of relations $\{0,1\}^{G \times G}$ endowed with the product topology and the closed subset $\mathrm {Ord}(G)$ of strict total orders $\prec $ on G. We will consider the action $G \curvearrowright \mathrm {Ord}(G)$ given by
for $h_1,h_2,g \in G$ and $\prec \in \mathrm {Ord}(G)$ . An invariant random order on G is a G-invariant Borel probability measure on $\mathrm {Ord}(G)$ . Notice that a fixed point for the action $G \curvearrowright \mathrm {Ord}(G)$ corresponds to a (deterministic) invariant order on G. The space of invariant random orders will be denoted by $\mathcal {M}_G(\mathrm {Ord}(G))$ .
Invariant random orders were introduced in [Reference Alpeev, Meyerovitch and Ryu1] to answer problems about predictability in topological dynamics through what they called the Kieffer–Pinsker formula for the Kolmogorov–Sinai entropy of a group action.
Now, as in the deterministic case, we can also define a notion of past for the group. An invariant random past on G is a random function $\tilde {\Phi }: G \to \{0,1\}^G$ or, equivalently, a Borel probability measure on $(\{0,1\}^G)^G$ that satisfies, for almost every instance of $\tilde {\Phi }$ , the following properties:
-
(1) for all $g \in G$ , the condition $g \notin \tilde {\Phi }(g)$ holds;
-
(2) for all $g,h \in G$ , if $g \in \tilde {\Phi }(h)$ , then $\tilde {\Phi }(g) \subseteq \tilde {\Phi }(h)$ ;
-
(3) if $g \neq h$ , then either $g \in \tilde {\Phi }(h)$ or $h \in \tilde {\Phi }(g)$ ; and
-
(4) for all $g \in G$ , the random subsets $\tilde {\Phi }(g)$ and $\tilde {\Phi }(1_G)g$ have the same distribution.
Notice that if $\prec $ is an invariant random order, then the random function $g \mapsto \{h \in G: h \prec g\}$ defines an invariant random past.
In contrast to deterministic invariant orders, every countable group G admits at least one invariant random total order. Namely, consider the random process $(\chi _g)_{g \in G}$ of independent random variables such that each $\chi _g$ has uniform distribution on $[0,1]$ . This process is invariant and each realization of it induces an order on G almost surely. We call such order the uniform random order.
7 Counting
From now on, given $(\Gamma ,\unicode{x3bb} ) \in \mathcal {H}_G$ , we always assume that there is some (or any) fixed fundamental domain $U_0$ for $G \curvearrowright \Gamma $ and we introduce the auxiliary function $\phi _\unicode{x3bb} : X(\Gamma ) \to \mathbb {R}$ given by
7.1 A pointwise Shannon–McMillan–Breiman-type theorem
The next theorem establishes a pointwise Shannon–McMillan–Breiman-type theorem for Gibbs measures (related results can be found in [Reference Briceño9, Reference Gurevich and Tempelman20]). To prove it, we use the pointwise ergodic theorem [Reference Lindenstrauss28], which requires tyhe Følner sequence $\{F_n\}_n$ to be tempered, a technical condition that is satisfied by every Følner sequence up to a subsequence and that we will assume without further detail.
Theorem 7.1. Let G be a countable amenable group. For every $(\Gamma ,\unicode{x3bb} ) \in \mathcal {H}_G$ and every $\mathbb {P} \in \mathcal {M}_{\mathrm {Gibbs}}(\Gamma ,\unicode{x3bb} )$ ,
for any tempered Følner sequence $\{F_n\}_n$ and any $\mathbb {Q} \in \mathcal {M}_G^{\mathrm {erg}}(X(\Gamma ))$ .
Proof. Consider the sets $U_n = F_nU_0$ and $M_n = U_n \cup \partial U_n$ . Notice that, by amenability, $\lim _{n \to \infty } {\lvert M_n \rvert }/{\lvert U_n \rvert } = 1$ . Indeed, define $K {\kern-1pt}={\kern-1pt} \{g {\kern-1pt}\in{\kern-1pt} G: \mathrm {dist}_\Gamma (U_0,gU_0) {\kern-1pt}\leq{\kern-1pt} 1\}$ . Then, $1_G \in K$ and $U_0 \cup \partial U_0 \subseteq KU_0$ . Since $\Gamma $ is locally finite and the action is free, K is finite. In addition, $U_n \cup \partial U_n \subseteq F_nKU_0$ . Therefore, by amenability,
so $\lim _n {\lvert \partial U_n \rvert }/{\lvert U_n \rvert } = 0$ . Fix independent sets $x \in X(\Gamma [U_n])$ , $z_1,z_2 \in X(\Gamma [M_n \setminus U_n])$ , and $y \in X(\Gamma )$ such that $xz_iy \in X(\Gamma )$ for $i = 1,2$ . Then,
Taking $z_2 = 0^\Gamma $ and adding over all possible $z_1$ , we obtain that
However, we have that
since
and $Z^{0^\Gamma }_\Gamma (M_n,\unicode{x3bb} ) = Z_\Gamma (M_n,\unicode{x3bb} )$ . In addition,
since
Therefore,
In particular, since $\mathbb {P}([x_{F_nU_0}]) = \mathbb {E}_{\mathbb {P}}(\mathbb {P}([x_{U_n}] \vert \mathcal {B}_{M_n^c})(y)) = \mathbb {E}_{\mathbb {P}}(\pi ^y_{M_n}([x_{U_n}]))$ , we have that
so
Now, since $\mathrm {w}^{0^\Gamma }_\unicode{x3bb} (x_{M_n},M_n) = \mathrm {w}_\unicode{x3bb} (x_{M_n},M_n)$ for every x, we have that
Therefore,
so
and we conclude that
where we have used that $Z_\Gamma (U_n,\unicode{x3bb} ) \leq Z_\Gamma (M_n,\unicode{x3bb} ) \leq (2\max \{1,\unicode{x3bb} _+\})^{\lvert M_n \setminus U_n \rvert }Z_\Gamma (U_n,\unicode{x3bb} )$ . Finally, notice that
and by the pointwise ergodic theorem, we obtain that
so
and we conclude the proof.
We have the following lemma.
Lemma 7.2. Given $\Delta \in \mathbb {N}$ and $(\Gamma ,\unicode{x3bb} ) \in \mathcal {H}^\Delta $ , there exists a constant $C\hspace{-1pt} =\hspace{-1pt} C(\Delta ,\unicode{x3bb} _-, \unicode{x3bb} _+)> 0$ such that for every $U \Subset V(\Gamma )$ , $x \in X(\Gamma )$ , and $v \in U$ ,
Proof. Fix $(\Gamma ,\unicode{x3bb} ) \in \mathcal {H}_G^\Delta $ , $U \Subset V(\Gamma )$ , $x \in X(\Gamma )$ , and $v \in U$ . Notice that if $U^c \cap \partial \{v\} \neq \emptyset $ and $u \in U^c \cap \partial \{v\}$ is such that $x(u) = 1$ , then necessarily $x_v = 0^v$ and $\pi ^x_U([x_v]) = 1$ . However, if $U \cap \partial \{v\} = \emptyset $ , then $\pi ^x_U([x_v]) = \mathbb {P}_{\Gamma [U'],\unicode{x3bb} }([x_v])$ for $U' = U \setminus \{u \in U: x(u') = 1 \text { for some } u' \in U^c \cap \partial \{u\}\}$ , so, by Lemma 5.3,
Therefore, by taking $C = \min \{1, {\min \{1,\unicode{x3bb} _-\}}/({\unicode{x3bb} _- + (1+\unicode{x3bb} _+)^\Delta })\} = {\min \{1,\unicode{x3bb} _-\}}/ (\unicode{x3bb} _- + (1+\unicode{x3bb} _+)^\Delta )$ , we conclude.
7.2 A randomized sequential cavity method
Suppose now that $(\Gamma ,\unicode{x3bb} ) \in \mathcal {H}_G$ is such that the Gibbs $(\Gamma ,\unicode{x3bb} )$ -specification satisfies SSM and let $\mathbb {P}$ be the unique Gibbs measure. Considering this, we define the function $I_{\mathbb {P}}: X(\Gamma ) \times (\{0,1\}^G)^G \to \mathbb {R}$ given by
where
and $\{F_n\}_n$ is any exhaustion of G (not necessarily Følner). Here, $\Phi \in (\{0,1\}^G)^G$ should be understood as an instance of a random invariant past and $I_{\mathbb {P},n}$ as a rudimentary information function. In this sense, notice that $I_{\mathbb {P},n}(x,\Phi )$ only depends on the values of x restricted to $\Phi (1_G) \in \{0,1\}^G$ , so $\Phi $ carries redundant information. This redundancy will play a role in the next results when taking averages.
Lemma 7.3. If $(\Gamma ,\unicode{x3bb} ) \in \mathcal {H}_G$ is such that the Gibbs $(\Gamma ,\unicode{x3bb} )$ -specification satisfies SSM and $\mathbb {P}$ is the unique Gibbs measure, then the function $I_{\mathbb {P}}$ is measurable, non-negative, defined everywhere, and bounded. Moreover,
Proof. Since $\mathbb {P}([x_{U_0}] \vert [x_{(\Phi (1_G) \cap F_n)U_0}])$ depends on finitely many coordinates in both $X(\Gamma )$ and $(\{0,1\}^G)^G$ , $0 < \mathbb {P}([x_{U_0}] \vert [x_{(\Phi (1_G) \cap F_n)U_0}]) < 1$ , and $-\log (\cdot )$ is a continuous function, $I_{\mathbb {P},n}$ is measurable and since $I_{\mathbb {P}}$ is a limit superior, it is measurable as well.
By SSM and Proposition 4.1,
is always a well-defined limit. By Lemma 7.2 and since $(\Gamma ,\unicode{x3bb} ) \in \mathcal {H}^\Delta _G$ for some $\Delta $ , there exists a constant $C> 0$ such that for every $v \in V$ , $U \Subset V \setminus \{v\}$ , and $x \in X(\Gamma )$ ,
Now, combined with the SSM property, this implies that for every $v \in V$ , $U \subseteq V$ , and $x \in X(\Gamma )$ , we have that
Indeed, if $v \in U$ , this is direct, since $\mathbb {P}([x_v] \vert [x_U]) = 1$ . However, if $v \notin U$ , by SSM,
Therefore, by conditioning and iterating, we obtain that
so
that is, $I_{\mathbb {P}}(x,\Phi )$ is bounded.
Following [Reference Alpeev, Meyerovitch and Ryu1], given an invariant random past $\tilde {\Phi }: G \to \{0,1\}^G$ on G with law $\tilde {\nu } \in \mathcal {M}_G((\{0,1\}^G)^G)$ , we denote
for $f \in L^1(\tilde {\nu })$ . Now, since $I_{\mathbb {P}}$ is measurable, non-negative, and bounded, we have that for every $\mathbb {Q} \in \mathcal {M}_G(X(\Gamma ))$ , the function $I_{\mathbb {P}}$ is integrable with respect to $\mathbb {Q} \times \tilde {\nu }$ and by Tonelli’s theorem, the function $\mathbb {E}_{\tilde {\Phi }}I_{\mathbb {P}}: X(\Gamma ) \to \mathbb {R}$ is integrable, defined $\mathbb {Q}$ -almost everywhere, and satisfies that
We call $\mathbb {E}_{\tilde {\Phi }}I_{\mathbb {P}}$ the random $\mathbb {P}$ -information function (with respect to $\tilde {\Phi }$ ).
Lemma 7.4. For any tempered Følner sequence $\{F_n\}_n$ , any invariant random past $\tilde {\Phi }$ , and any $\mathbb {Q} \in \mathcal {M}_G(X(\Gamma ))$ ,
for $\mathbb {Q}$ -almost every x.
Proof. Fix a (tempered) Følner sequence $\{F_n\}_n$ . By the properties of $\tilde {\Phi }$ , for $\tilde {\nu }$ -almost every instance $\Phi $ , every $F_n$ can be ordered as $g_1, \ldots ,g_{\lvert F_n \rvert }$ so that $\Phi (g_i) \cap F_n = \{g_1,\ldots ,g_{i-1}\}$ . Then,
Given $\ell> 0$ , let $K_\ell = \{g \in G: \mathrm {dist}_\Gamma (U_0,gU_0) \leq \ell \}$ . If $g \in \mathrm {Int}_{K_\ell }(F_n) = \{g \in G: K_\ell g \subseteq F_n\}$ , then
and
so
However, by Lemma 7.2 and the discussion after it, for every $g \in G$ and $U \subseteq V$ ,
Therefore, by the mean value theorem,
Notice that
so
Now, given $\epsilon> 0$ , there exists $\ell $ and $n_0$ such that for every $n \geq n_0$ ,
By G-invariance of $\mathbb {P}$ ,
and combining this fact with the previous estimate, we obtain that
Integrating against $\tilde {\nu }$ , we obtain that, for $\mathbb {Q}$ -almost every x,
and since $\tilde {\Phi }(g)$ has the same distribution as $\tilde {\Phi }(1_G)g$ , we get that
so
and since $\epsilon $ is arbitrary and the limit exists $\mathbb {Q}$ -almost surely, we conclude.
We have the following representation theorem for free energy, which can be regarded as a randomized generalization of the results in [Reference Briceño9, Reference Gamarnik and Katz16, Reference Marcus and Pavlov36] tailored for the specific case of the hardcore model. Notice that, in contrast with [Reference Briceño9, Reference Gamarnik and Katz16, Reference Marcus and Pavlov36], the representation holds in every amenable group and not just virtually orderable groups.
Theorem 7.5. Let $(\Gamma ,\unicode{x3bb} ) \in \mathcal {H}_G$ such that the Gibbs $(\Gamma ,\unicode{x3bb} )$ -specification satisfies SSM and $\mathbb {P}$ is the unique Gibbs measure. Then,
for any $\mathbb {Q} \in \mathcal {M}_G(X(\Gamma ))$ and for any invariant random past $\tilde {\Phi }$ of G. In particular,
Proof. First, notice that if the statement holds for every $\mathbb {Q} \in \mathcal {M}^{\mathrm {erg}}_G(X(\Gamma ))$ , then it holds for every $\mathbb {Q} \in \mathcal {M}_G(X(\Gamma ))$ by the ergodic decomposition theorem. Then, without loss of generality, we can assume that $\mathbb {Q}$ is G-ergodic. Considering this, by Theorem 7.1, for $\mathbb {Q}$ -almost every x,
By Lemma 7.4, for $\mathbb {Q}$ -almost every x,
Therefore, for $\mathbb {Q}$ -almost every x,
Integrating against $\mathbb {Q}$ , we obtain that
where the first equality is due to the dominated convergence theorem, the second and last equalities are due to Tonelli’s theorem, and the third equality is due to the G-invariance of $\mathbb {Q}$ . We conclude that
In particular, if $\mathbb {Q} = \delta _{0^\Gamma } \in \mathcal {M}_G(X(\Gamma ))$ , the Dirac measure supported on $0^\Gamma $ , then
7.3 An arboreal representation of free energy
The following theorem tell us that, under some special conditions, $f_G(\Gamma ,\unicode{x3bb} )$ can be expressed using $\lvert \Gamma / G \rvert $ terms depending on the probability that the roots of some particular trees are unoccupied. Roughly, the trees involved are the trees of self-avoiding walks that are rooted at the vertices of a given fundamental domain and explore the graph $\Gamma $ without entering to the ‘past graph’ induced by an invariant random past.
Theorem 7.6. Let $(\Gamma ,\unicode{x3bb} ) \in \mathcal {H}_G$ such that the Gibbs $(T_{\mathrm {SAW}}(\Gamma ,v),\overline {\unicode{x3bb} })$ -specification satisfies SSM for every $v \in V(\Gamma )$ and let $v_1,\ldots ,v_{\lvert \Gamma / G \rvert }$ be an arbitrary ordering of a fundamental domain $U_0$ . Given an invariant random past $\tilde {\Phi }$ of G, denote by $\Gamma _i(\tilde {\Phi })$ the random graph given by $\Gamma \setminus (\tilde {\Phi }(1_G)U_0 \cup \{v_1,\ldots ,v_{i-1}\})$ . Then,
where $\rho _i$ denotes the root of $T_{\mathrm {SAW}(\Gamma _i(\Phi ),v_i)}$ . In particular, if $\prec $ is a deterministic invariant order of G,
Proof. By Theorem 7.5, we know that
By iterating conditional probabilities, linearity of expectation, and Proposition 4.1 (see Figure 4),
Finally, by Theorem 5.6, we obtain
In particular, if $\prec $ is a deterministic invariant order on G (see Figure 5), we have that
8 A computational phase transition in the thermodynamic limit
Given an amenable countable group G, we are interested in having an algorithm to efficiently approximate $f_G(\Gamma ,\unicode{x3bb} )$ in some uniform way over $\mathcal {H}_G$ .
Let $\mathbb {M} \subseteq \mathcal {H}_G$ be a family of hardcore models. We will say that $\mathbb {M}$ admits an additive fully polynomial-time randomized approximation scheme (additive FPRAS) for $f_G(\Gamma ,\unicode{x3bb} )$ if there is a probabilistic algorithm such that given an input $(\Gamma ,\unicode{x3bb} ) \in \mathbb {M}$ and $\epsilon> 0$ , outputs $\hat {f}$ with
in polynomial time in $\lvert \langle\Gamma ,\unicode{x3bb}\rangle \rvert $ and $\epsilon ^{-1}$ , where $\lvert \langle\Gamma ,\unicode{x3bb}\rangle \rvert $ denotes the length of any reasonable representation $\langle\Gamma ,\unicode{x3bb}\rangle$ of $(\Gamma ,\unicode{x3bb} )$ . Similarly, we will say that $\mathbb {M}$ admits an additive fully polynomial-time approximation scheme (additive FPTAS) for $f_G(\Gamma ,\unicode{x3bb} )$ if there is a deterministic additive FPRAS with null failure probability.
An additive FPRAS and an additive FPTAS will be what we will regard as an efficient and uniform approximation algorithm for $f_G(\Gamma ,\unicode{x3bb} )$ , random and deterministic, respectively.
Remark 8.1. The constant $\tfrac 34$ in the definition of additive FPRAS is the standard choice for minimum success probability but it can be replaced by any constant bounded away from $\tfrac 12$ without any sensible change in the definition. To not have to deal with numerical details about the representation of $\unicode{x3bb} $ , we will always implicitly assume that the values taken by $\unicode{x3bb} $ have a bounded number of digits uniformly on $\mathbb {M}$ .
8.1 Weitz’s algorithm and a computational phase transition
Observe that if G is the trivial group $\{1\}$ , then $\mathcal {H}_{\{1\}}$ is exactly the family of finite hardcore models. In this case, we have that
and we can translate an approximation of $Z_\Gamma (\unicode{x3bb} )$ into an approximation of $f_G(\Gamma ,\unicode{x3bb} )$ and vice versa.
In this finite context, it is common to consider a fully polynomial-time approximation scheme. Given a family $\mathbb {M} \subseteq \mathcal {H}_{\{1\}}$ of finite hardcore models, we will say that $\mathbb {M}$ admits an FPTAS for $Z_\Gamma (\unicode{x3bb} )$ if there is an algorithm such that, given an input $(\Gamma ,\unicode{x3bb} ) \in \mathbb {M}$ and $\epsilon> 0$ , outputs $\hat {Z}$ with
in polynomial time in $\lvert V(\Gamma ) \rvert $ and $\epsilon ^{-1}$ . An FPTAS is regarded as an efficient and uniform approximation algorithm for $Z_\Gamma (\unicode{x3bb} )$ .
If we take logarithms and divide by $\lvert V(\Gamma ) \rvert $ in the previous equation, we obtain that
where $\hat {f} = {\log \hat {Z}}/{\lvert V(\Gamma ) \rvert }$ , so an FTPAS for $Z_\Gamma (\unicode{x3bb} )$ is equivalent to an additive FPTAS for $f_G(\Gamma ,\unicode{x3bb} )$ , since a polynomial in $\lvert V(\Gamma ) \rvert $ and $\epsilon ^{-1}$ is also a polynomial in $\lvert \langle\Gamma ,\unicode{x3bb}\rangle \rvert $ and $\lvert V(\Gamma ) \rvert \epsilon ^{-1}$ and vice versa. The same correspondence holds between the natural randomized counterparts (FPRAS and additive FPRAS, respectively).
We will fix a positive integer $\Delta $ and $\unicode{x3bb} _0> 0$ . Given these parameters, we aim to develop a fully polynomial-time additive approximation on $\mathbb {M} = \mathcal {H}_G^\Delta (\unicode{x3bb} _0)$ .
The main theorem in [Reference Weitz55] was the development of an FPTAS for $Z_\Gamma (\unicode{x3bb} _0)$ on $\mathcal {H}_{\{1\}}^\Delta (\unicode{x3bb} _0)$ for $\unicode{x3bb} _0 < \unicode{x3bb} _c(\Delta )$ . It is not difficult to see that the theorem extends to non-constant activity functions $\unicode{x3bb} $ . Then, and also translated into the language of free energy, we have the following result.
Theorem 8.2. [Reference Weitz55]
For every $\Delta \in \mathbb {N}$ and $0 < \unicode{x3bb} _0 < \unicode{x3bb} _c(\Delta )$ , there exists an FPTAS (respectively additive FPTAS) on $\mathcal {H}_{\{1\}}^\Delta (\unicode{x3bb} _0)$ for $Z_\Gamma (\unicode{x3bb} )$ (respectively for $f_G(\Gamma ,\unicode{x3bb} )$ ).
This theorem was subsequently refined in [Reference Sinclair, Srivastava, Štefankovič and Yin46] by considering connective constants instead of maximum degree $\Delta $ . A very interesting fact is that when classifying graphs according to their maximum degree, then Theorem 8.2 is in some sense optimal due to the following theorem.
Theorem 8.3. [Reference Sly48, Reference Sly and Sun49]
For every $\Delta \geq 3$ and $\unicode{x3bb} _0> \unicode{x3bb} _c(\Delta )$ , there does not exist an FPRAS (respectively an additive FPRAS) on $\mathcal {H}_{\{1\}}^\Delta (\unicode{x3bb} _0)$ for $Z_\Gamma (\unicode{x3bb} _0)$ (respectively for $f_G(\Gamma ,\unicode{x3bb} _0)$ ), unless $\mathrm {NP} = \mathrm {RP}$ .
Remark 8.4. Notice that the lack of existence of an FPRAS (respectively additive FPRAS) directly implies the lack of existence of an FPTAS (respectively additive FPTAS).
The combination of Theorems 8.2 and 8.3 is what is regarded as a computational phase transition. We aim to extend these theorems to the infinite setting. A theoretical advantage about considering $f_G(\Gamma ,\unicode{x3bb} )$ instead of $Z_\Gamma (\unicode{x3bb} )$ is that the free energy still makes sense in infinite graphs and, at the same time, recovers the theory for $Z_\Gamma (\unicode{x3bb} )$ in the finite case.
8.2 An extension of Weitz’s algorithm to the infinite setting
For algorithmic purposes, in this section, we only consider finitely generated groups G with a fixed symmetric set of generators S. In this case, if $(\Gamma ,\unicode{x3bb} ) \in \mathcal {H}_{G}^\Delta $ , then it suffices to know $\Gamma [U_0]$ for some fundamental domain $U_0$ and $L = \{(v_1,s,v_2) \in U_0 \times S \times U_0: (v_1,sv_2) \in E(\Gamma )\}$ to fully reconstruct the graph $\Gamma $ . In particular, the size of the necessary information to reconstruct $\Gamma $ is bounded by a polynomial in $\Delta $ and $\lvert \Gamma / G \rvert $ . In addition, given a G-invariant activity function $\unicode{x3bb} : V(\Gamma ) \to \mathbb {Q}_{>0}$ (that is, that only takes positive rational values), we only need to know $\unicode{x3bb} \vert _{U_0}$ to recover $\unicode{x3bb} $ , that is, just $\lvert \Gamma / G \rvert $ many rational numbers. Therefore, in this context, the length $\lvert \langle\Gamma ,\unicode{x3bb}\rangle \rvert $ of the representation $\langle \Gamma ,\unicode{x3bb} \rangle$ of a hardcore model $(\Gamma , \unicode{x3bb} )$ will be polynomial in $\Delta $ and $\lvert \Gamma / G \rvert $ .
First, we are interested in being able to generate in an effective way balls of arbitrary radius in $\mathrm {Cay}(G,S)$ . Given an input word $w \in S^*$ , we will assume that we can decide whether $e(w) = 1_G$ or not in time $\exp (O(\lvert w \rvert ))$ , where $\lvert w \rvert $ denotes the length of w, $e: S^* \to G$ is the usual evaluation map, and the O-notation regards $\lvert S \rvert $ and $\Delta $ as constants. In other words, we will assume that the word problem of G can be solved in exponential time. By problems that can be solved in exponential time, we mean the set of decision problems that can be solved by a deterministic Turing machine in time $\exp (O(n))$ . This complexity class is sometimes known as $\mathrm {E}$ ; it contains $\mathrm {P}$ and it is strictly contained in $\mathrm {EXP}$ .
Now, if the word problem can be solved in exponential time, then $\mathrm {Cay}(G,S)$ is constructible in time $\exp (O(\ell ))$ as well (see [Reference Meier37, Theorem 5.10]); this is to say, given $\ell> 0$ , we can generate $B_{\mathrm {Cay}(G,S)}(1_G,\ell )$ in time $\exp (O(\ell ))$ . Having that, it is possible to construct $\Gamma [B_{\mathrm {Cay}(G,S)}(1_G,\ell )U_0]$ in time $O(\mathrm {poly}(\lvert \Gamma / G \rvert )\exp (O(\ell )))$ by identifying each $g \in B_{\mathrm {Cay}(G,S)}(1_G,\ell )$ with a copy $\Gamma [gU_0]$ of $\Gamma [U_0]$ and by connecting it to other adjacent copies according to L.
In the ordered case, we will also consider the situation where the algebraic past of $(G,\prec )$ can be decided in exponential time, that is, given an input word $w \in S^*$ , we will consider that we can decide whether $e(w) \in \Phi _\prec $ or not in time $\exp (O(\lvert w \rvert ))$ . Notice that this implies that the word problem can be solved in time $\exp (O(\lvert w \rvert ))$ , since $e(w) = 1_G$ if and only if $e(w) \notin \Phi _\prec $ and $e(w^{-1}) \notin \Phi _\prec $ . In particular, and since $\lvert B_{\mathrm {Cay}(G,S)}(1_G,\ell ) \rvert \leq \lvert S \rvert ^\ell $ , by identifying and removing all the copies $\Gamma [gU_0]$ with $g \in \Phi _\prec $ in $\Gamma [B_{\mathrm {Cay}(G,S)}(1_G,\ell )U_0]$ , we can construct $\Gamma [(B_{\mathrm {Cay}(G,S)}(1_G,\ell ) \setminus \Phi _\prec )U_0]$ in time $O(\mathrm {poly}(\lvert \Gamma / G \rvert )\exp (O(\ell )))$ . Recall that we are not losing generality if we assume G to be ordered instead of just virtually ordered.
Considering all this, we have the following key theorem.
Theorem 8.5. Let G be a finitely generated amenable group such that its word problem can be solved in exponential time. Then, for every $\Delta \in \mathbb {N}$ and $0 < \unicode{x3bb} _0 < \unicode{x3bb} _c(\Delta )$ , there exists an additive FPRAS on $\mathcal {H}_G^\Delta (\unicode{x3bb} _0)$ for $f_G(\Gamma ,\unicode{x3bb} )$ . If, in addition, G is orderable and has an algebraic past that can be decided in exponential time, then the algorithm can be chosen to be deterministic, that is, an additive FPTAS.
Proof. Pick $(\Gamma ,\unicode{x3bb} )$ as in the statement and enumerate as $U_0 = \{v_1,\ldots ,v_n\}$ the fundamental domain of $G \curvearrowright \Gamma $ . Denote $n = \lvert \Gamma / G \rvert $ . Then, by Theorem 7.5,
where $\Gamma _i(\tilde {\Phi }) = \Gamma \setminus (\tilde {\Phi }(1_G)U_0 \cup \{v_1,\ldots ,v_{i-1}\})$ and $\tilde {\Phi }$ is any invariant random past of G. Let $f_i = -\mathbb {E}_{\tilde {\Phi }}\log \mathbb {P}_{\Gamma _i(\tilde {\Phi }),\unicode{x3bb} }([0^{v_i}])$ . Given $\epsilon> 0$ , our goal is to generate numbers $\hat {f}_i$ such that
for every $i = 1,\ldots ,n$ . If we manage to obtain these approximations, we have that
so $\hat {f} := \sum _{i=1}^n \hat {f}_i$ will be the required approximation. By SSM in $\Gamma $ , we have that, for every $\ell> 0$ ,
and, again by SSM but now on the tree of self-avoiding walks,
where C is a constant that depends on $\Delta $ and $\unicode{x3bb} _0$ . Notice that $T_{\mathrm {SAW}}(\Gamma _i(\tilde {\Phi }) \cap B_\Gamma (v_i,\ell ),v_i)\cap B(\rho _i,\ell ) = T_{\mathrm {SAW}}(\Gamma _i(\tilde {\Phi }),v_i)\cap B(\rho _i,\ell )$ , so
To conclude, it suffices to define $\hat {f}_i$ as $\mathbb {E}_{\tilde {\Phi }}\log \mathbb {P}_{T_{\mathrm {SAW}}( \Gamma _i(\tilde {\Phi }),v_i)\cap B(\rho _i,\ell ),\overline {\unicode{x3bb} }}([0^{\rho _i}])$ with $\ell $ so that $2C\exp (-\alpha \ell ) \leq \frac {\epsilon }{n}$ and show that each approximation $\hat {f}_i$ can be efficiently computed. Notice that we can pick $\ell $ to be $\ell ^* = \lceil {1}/{\alpha }\log (2Cn\epsilon ^{-1})\rceil $ .
Let us first assume that $\tilde {\Phi }$ is a (deterministic) algebraic past $\Phi _\prec $ of G that can be decided in exponential time. The general probabilistic case will be a slight variation of this case. To compute $\hat {f}_i$ , first generate the ball $\Gamma [B_{\mathrm {Cay}(G,S)}(1_G,\ell ^*)U_0]$ , which takes time $\mathrm {poly}(n)\exp (O(\ell ^*)) = \mathrm {poly}((1+\epsilon ^{-1})n)$ . Notice that $B_{\Gamma }(v_i,\ell ) \subseteq B_{\mathrm {Cay}(G,S)}(1_G,\ell ^*)U_0$ . Next, remove the vertices that are at a distance greater than $\ell ^*$ to $v_i$ and those which belong to $\Phi _\prec U_0 \cup \{v_1,\ldots ,v_{i-1}\}$ . This procedure also takes time $\mathrm {poly}(n)\exp (O(\ell ^*))$ , since $\Phi _\prec $ can be decided in exponential time. Having this, construct the tree of self-avoiding walks $T_i := T_{\mathrm {SAW}}(\Gamma _i(\Phi _\prec ),v_i) \cap B(\rho _i,\ell ^*)$ (which is a subtree of the tree of self-avoiding walks of $\Gamma _i(\Phi _\prec )$ ). Using the recursive procedure, compute $\mathbb {P}_{T_i,\overline {\unicode{x3bb} }}([0^{\rho _i}])$ and then compute its logarithm. For every $i = 1,\ldots ,n$ ,
which is also a bound for the order of time required for computing $\hat {f}_i$ , because $T_i$ is a tree (see Figure 5). Finally, since we require to do this procedure n times for each $i = 1,\ldots ,n$ , we have that the total order of the algorithm is still $\mathrm {poly}((1+\epsilon ^{-1})n)$ , that is, a polynomial in n and $\epsilon ^{-1}$ , where the constants involved depend only on $\Delta $ , $\unicode{x3bb} _0$ , and $\lvert S \rvert $ . This gives the desired additive FPTAS in the ordered case.
Now, in the general not necessarily ordered case, we consider the following variation of the previous algorithm. Let $\tilde {\Phi }_{\mathrm { unif}}$ be the uniform random order in G. Then,
with $m = \lvert B_{\mathrm {Cay}(G,S)}(v_i,\ell ) \rvert -1$ . Consider the random variable X with probability distribution $\mathbb {P}(X = -\log \mathbb {P}_{\Gamma _i(\Phi ) \cap B_\Gamma (v_i,\ell ),\unicode{x3bb} }([0^{v_i}])) = {1}/{2^m}$ for $\Phi \subseteq B_{\mathrm {Cay}(G,S)}(1_G,\ell ) \setminus \{1_G\}$ . Then, $\mathbb {E}[X] = -\mathbb {E}_{\tilde {\Phi }_{\mathrm { unif}}}\log \mathbb {P}_{\Gamma _i(\tilde {\Phi }_{\mathrm { unif}}) \cap B_\Gamma (v_i,\ell ),\unicode{x3bb} }([0^{v_i}])$ . Due to Lemma 5.3, we have that
In particular,
Now, let $\{X_{1}, \ldots , X_{N}\}$ be a random sample of size N of the variable X and define the sample average $\bar {X}_N \equiv {1}/{N} \sum _{j=1}^N X_j$ . Notice that $\mathbb {E}[\bar {X}_N] = \mathbb {E}[X]$ and $\mathrm {Var}(\bar {X}_N) = {1}/{N} \mathrm {Var}(X) \leq {V(\unicode{x3bb} ,\Delta )}/{N}$ . Therefore, by Chebyshev’s inequality, for any $\delta> 0$ ,
We are interested in having $\lvert \bar {X}_N-\mathbb {E}[X] \rvert \leq {\epsilon }/{n}$ with probability greater than $\tfrac 34$ . To guarantee this, we need to take a number of samples N so that
and $\delta $ such that $1-\delta \geq \tfrac 34$ , that is, it suffices to take $N \geq 4V(\unicode{x3bb} ,\Delta )(n\epsilon ^{-1})^2$ . Notice that we need to take a number of samples polynomial in n and $\epsilon ^{-1}$ , and that each sample can be computed in polynomial time, exactly as in the ordered case. This gives the desired additive FPRAS in the general case.
Remark 8.6. Notice that Theorem 8.5 holds for groups of exponential growth, despite it involving a polynomial time algorithm. In addition, in virtue of Theorem 5.8, the families of graphs in Theorem 8.5 could be parameterized according to their connective constant instead of the maximum degree.
Next, we reduce the problem of approximating the partition function of a finite hardcore model to the problem of approximating the free energy of a hardcore model in $\mathcal {H}_G$ .
Proposition 8.7. Let G be an amenable group. Then, for every $\Delta \geq 3$ and $\unicode{x3bb} _0> \unicode{x3bb} _c(\Delta )$ , there does not exist an additive FPRAS on $\mathcal {H}_G^\Delta (\unicode{x3bb} _0)$ for $f_G(\Gamma ,\unicode{x3bb} _0)$ , unless $\mathrm {NP} = \mathrm {RP}$ .
Proof. Suppose that we have an additive FPRAS on $\mathcal {H}_G^\Delta (\unicode{x3bb} _0)$ for $f_G(\Gamma ,\unicode{x3bb} )$ for some amenable group G. Then, we claim that we would have an FPRAS on $\mathcal {H}_{\{1\}}^\Delta (\unicode{x3bb} _0)$ for $Z_\Gamma (\unicode{x3bb} _0)$ , contradicting Theorem 8.3. Indeed, given the input $(\Gamma ,\unicode{x3bb} ) \in \mathcal {H}_{\{1\}}^\Delta (\unicode{x3bb} _0)$ , it suffices to consider the graph $\Gamma ^G$ made out of copies $\{\Gamma _g\}_{g \in G}$ of $\Gamma $ indexed by $g \in G$ , where $v_g$ denotes the copy in $\Gamma _g$ of the vertex v in $\Gamma $ . Then, there is a natural action $G \curvearrowright \Gamma ^G$ consisting of just translating copies of vertices, that is, $gv_h = v_{hg}$ , and a fundamental domain of the action is $U_0 = V(\Gamma _{1_G})$ . Therefore, since $\lvert \Gamma ^G / G \rvert = \lvert V(\Gamma ) \rvert $ , if we could $\epsilon $ -approximate in an additive way $f_G(\Gamma ,\unicode{x3bb} _0)$ in polynomial time in $\lvert \Gamma ^G / G \rvert $ and $\epsilon ^{-1}$ , then we would be able to $\epsilon $ -approximate in a multiplicative way $Z_\Gamma (\unicode{x3bb} _0)$ in polynomial time in $\lvert V(\Gamma ) \rvert $ and $\epsilon ^{-1}$ , because
but this contradicts Theorem 8.3.
Considering Theorem 8.5 and Proposition 8.7, we have the following corollary.
Corollary 8.8. Let G be a finitely generated amenable group such that its word problem can be solved in exponential time. Then, for every $\Delta \geq 3$ and $\unicode{x3bb} _0> 0$ , if $\unicode{x3bb} _0 < \unicode{x3bb} _c(\Delta )$ , there exists an additive FPRAS on $\mathcal {H}_G^\Delta (\unicode{x3bb} _0)$ for $f_G(\Gamma ,\unicode{x3bb} )$ . If, in addition, G has a finite index orderable subgroup such that its algebraic past can be decided in exponential time, then the algorithm can be chosen to be deterministic, that is, there exists an additive FPTAS on $\mathcal {H}_G^\Delta (\unicode{x3bb} _0)$ for $f_G(\Gamma ,\unicode{x3bb} )$ . However, if $\unicode{x3bb} _0> \unicode{x3bb} _c(\Delta )$ , there is no additive FPRAS on $\mathcal {H}_G^\Delta (\unicode{x3bb} _0)$ for $f_G(\Gamma ,\unicode{x3bb} )$ , unless $\mathrm {NP} = \mathrm {RP}$ .
Remark 8.9. Notice that Corollary 8.8 still holds for $\Delta = 1$ and $\Delta = 2$ . The first case is trivial and in the second case, there is no phase transition and the conditions for the existence of an additive FPRAS (respectively additive FPTAS) hold for every $\unicode{x3bb} _0$ .
To ask that the word problem can be solved in exponential time seems to be a natural requirement for having an efficient algorithm for approximating $f_G(\Gamma ,\unicode{x3bb} )$ and, fortunately, there are several classes of finitely generated groups which satisfy this condition.
Example 8.10. Lipton and Zalcstein [Reference Lipton and Zalcstein29] proved that every linear group over a field of characteristic zero has a word problem that can be solved in logarithmic space. This result was extended by Simon [Reference Simon45] to linear groups over a field of prime characteristic. In particular, the word problem of all finitely generated amenable linear groups—which by the Tits alternative [Reference Tits52] must be virtually solvable—can be solved in logarithmic space, and therefore polynomial time.
Due to a result from Mal’tsev [Reference Mal’tsev33], all solvable subgroups of the integer general linear group $\mathrm {GL}_d(\mathbb {Z})$ are polycyclic (that is, solvable groups in which every subgroup is finitely generated) and virtually polycyclic groups coincide with the class of polycyclic-by-finite groups, which are always finitely presented, residually finite, and have many other desirable algorithmic properties (see [Reference Baumslag, Cannonito, Robinson and Segal5]). However, Auslander [Reference Auslander3] and Swan [Reference Swan51] proved that any polycyclic group is a subgroup of the integer general linear group. This shows that the class of polycyclic groups is a general and natural setup for the application of our results, since they are amenable, finitely generated, and their word problem can be solved in polynomial time. Examples of polycyclic groups include all finitely generated abelian groups and all finitely generated nilpotent groups.
To understand how to guarantee the existence of an algebraic past that can be decided in exponential time, we start by observing two basic facts: (1) the group of integers $\mathbb {Z}$ is orderable with the natural order and its algebraic past can be decided in linear time and (2) the following lemma.
Lemma 8.11. Let $(H_1,\prec _1)$ and $(H_2,\prec _2)$ be two ordered groups and let G be a finitely generated group which is an extension of $H_2$ by $H_1$ , that is, there is a short exact sequence
Then, G can be ordered by considering the algebraic past $\Phi := \iota (\Phi _1) \cup \pi ^{-1}(\Phi _2)$ , where $\Phi _i$ denotes the algebraic past of $H_i$ for $i=1,2$ . In particular, if $\iota (\Phi _1)$ and $\pi ^{-1}(\Phi _2)$ can be decided in exponential time, then $\Phi $ can be decided in exponential time as well.
Proof. Consider the set $\Phi := \iota (\Phi _1) \cup \pi ^{-1}(\Phi _2)$ . It suffices to check that $\Phi $ is a semigroup (that is, $\Phi ^2 \subseteq \Phi $ ) and $G = \Phi \sqcup \{1_G\} \sqcup \Phi ^{-1}$ . Indeed, since $\iota (H_1) = \pi ^{-1}(1_{H_2})$ , we have that
However, since $\iota (\Phi _1) \subseteq \iota (H_1) = \pi ^{-1}(1_{H_2})$ and $\Phi _i^2 \subseteq \Phi _i$ for $i=1,2$ ,
Therefore, $\Phi $ is an algebraic past for G and it induces the invariant order $\prec $ , where $g \prec h$ for $h,g \in G$ if and only if $\pi (gh^{-1}) \prec _2 1_{H_2}$ or [ $\pi (gh^{-1}) = 1_{H_2}$ and $gh^{-1} \in \iota (\Phi _1)$ ]. In particular, if $\iota (\Phi _1)$ and $\pi ^{-1}(\Phi _2)$ can be decided in exponential time, then it is direct that $\Phi $ can also be decided in exponential time.
The previous lemma can be used as a tool for constructing algebraic pasts that can be decided in exponential time in new groups out of simpler ones. We have the following example.
Example 8.12. By the fundamental theorem of finitely generated abelian groups, every finitely generated abelian group G is isomorphic to a group of the form $\mathbb {Z}^d \oplus \mathbb {Z}_{q_1} \oplus \cdots \oplus \mathbb {Z}_{q_t}$ , where $d \geq 0$ is the rank and $q_1, \ldots , q_t$ are powers of prime numbers. In particular, $[G:\mathbb {Z}^d]$ is finite, so $\mathbb {Z}^d$ is a finite index subgroup of G. However, $\mathbb {Z}^d$ is an orderable group. A canonical presentation of $\mathbb {Z}^d$ is given by
where $[g, h] = ghg^{-1}h^{-1}$ is the commutator of g and h. A normal form for $\mathbb {Z}^d$ is given by $\{a_1^{i_1}\cdots a_d^{i_d}: i_1,\ldots ,i_d \in \mathbb {Z}\}$ and, given any word $w \in \{a^{\pm 1}_1,\ldots ,a^{\pm 1}_d\}^*$ , it takes linear time to obtain its normal form. A canonical order of $\mathbb {Z}^d$ is the lexicographic order $\prec $ , where we declare $a_1^{i_1}\cdots a_d^{i_d} \prec a_1^{j_1}\cdots a_d^{j_d}$ if $i_k < j_k$ for some $1 \leq k \leq d$ and $i_m = j_m$ for $m < k$ , where $<$ is the usual order in $\mathbb {Z}$ . It is easy to see that it can be decided in polynomial time whether $a_1^{i_1}\cdots a_d^{i_d} \prec a_1^{0}\cdots a_d^{0}$ or not. An alternative way to see this is through Lemma 8.11, by observing that $\mathbb {Z}^d$ is an extension of $\mathbb {Z}^{d-1}$ by $\mathbb {Z}$ and proceed inductively until reaching the base case $\mathbb {Z}^1 = \mathbb {Z}$ .
Another illustrative example is the discrete Heisenberg group:
The group $H_3(\mathbb {Z})$ is a non-abelian nilpotent (and therefore amenable with polynomial growth) finitely generated group. A presentation of $H_3(\mathbb {Z})$ is given by
where we identify a, b, and c with
respectively. A normal form for $H_3(\mathbb {Z})$ is given by $\{b^jc^ka^i: i,j,k \in \mathbb {Z}\}$ , where
It is not difficult to check that given a word $w \in \{a^{\pm 1},b^{\pm 1},c^{\pm 1}\}^*$ in its normal form and a generator $s \in \{a^{\pm 1},b^{\pm 1},c^{\pm 1}\}$ , it takes linear time to write $sw$ in its normal form. Observe that it is enough to measure how much time it takes this particular operation and then proceed inductively. Now, it is known that $H_3(\mathbb {Z})$ is an extension of $\mathbb {Z}^2$ by $\mathbb {Z}$ , that is,
with $\iota : \mathbb {Z} \longrightarrow H_3(\mathbb {Z})$ and $\pi : H_3(\mathbb {Z}) \longrightarrow \mathbb {Z}^2$ given by $\iota (k) = c^k$ and $\pi (b^{j} c^{z} a^{i}) = (i,j)$ , respectively. Considering Lemma 8.11 and that $\mathbb {Z}$ and $\mathbb {Z}^2$ have algebraic pasts $\Phi _{\mathbb {Z}}$ and $\Phi _{\mathbb {Z}^2}$ , respectively, such that $\iota (\Phi _{\mathbb {Z}})$ and $\pi ^{-1}(\Phi _{\mathbb {Z}^2})$ can be decided in exponential time, we conclude that $H_3(\mathbb {Z})$ also has an algebraic past that can be decided in exponential time. More concretely, this algebraic past $\Phi _{H_3(\mathbb {Z})}$ is defined by declaring that $b^jc^ka^i \in \Phi _{H_3(\mathbb {Z})}$ if and only if (1) $i < 0$ or (2) $i = 0$ and $j < 0$ or (3) $i=j=0$ and $k < 0$ , which takes linear time to decide.
Finally, one other example is the case of the Baumslag–Solitar group $BS(1,2)$ . A presentation of $BS(1,2)$ is given by $\langle a, b \mid bab^{-1}a^{-2}\rangle $ , where we identify a and b with the linear functions $x \mapsto 2x$ and $x \mapsto x+1$ in $\mathrm {Homeo}(\mathbb {R})$ , respectively. The group $BS(1,2)$ is a non-nilpotent solvable (and therefore amenable with exponential growth) finitely generated group. A normal form for $BS(1,2)$ is given by $\{a^{-j}b^{2k+1}a^{j+i}: i,j,k \in \mathbb {Z}\} \cup \{a^i: i \in \mathbb {Z}\}$ and it can also be checked that given a word $w \in \{a^{\pm 1},b^{\pm 1}\}^*$ in its normal form and a generator $s \in \{a^{\pm 1},b^{\pm 1}\}$ , it takes polynomial time to write $sw$ in its normal form. It is known that $BS(1,2)$ is an extension of $\mathbb {Z}$ by $\mathbb {Z}[\tfrac 12]$ , the group of dyadic rationals, that is,
with $\iota : \mathbb {Z}[\tfrac 12] \longrightarrow BS(1,2)$ and $\pi : BS(1,2) \longrightarrow \mathbb {Z}$ given by $\iota (({2k+1})/{2^j}) = a^{-j}b^{2k+1}a^{j}$ , and $\pi (a^{-j}b^{2k+1}a^{j+i}) = i$ and $\pi (a^{i}) = i$ , respectively. Then, due to Lemma 8.11 and the fact that $\mathbb {Z}[\tfrac 12]$ and $\mathbb {Z}$ have algebraic pasts $\Phi _{\mathbb {Z}[1/2]}$ and $\Phi _{\mathbb {Z}}$ , respectively, such that $\iota (\Phi _{\mathbb {Z}[1/2]})$ and $\pi ^{-1}(\Phi _{\mathbb {Z}})$ can be decided in exponential time, we conclude that $BS(1,2)$ also has an algebraic past $\Phi _{BS(1,2)}$ that can be decided in exponential time. More concretely, this algebraic past is defined by declaring that $a^{-j}b^{2k+1}a^{j+i} \in \Phi _{BS(1,2)}$ if and only if (1) $i < 0$ or (2) $i = 0$ and $k < 0$ , which takes linear time to decide. This construction can be easily generalized to the group $BS(1,n)$ given by the presentation $\langle a, b \mid bab^{-1}a^{-n}\rangle$ .
The previous facts about word problems and algebraic pasts give us general conditions for efficiently generating $\Gamma [B_{\mathrm {Cay}(G,S)}(1_G,\ell )U_0]$ and $\Gamma [(B_{\mathrm {Cay}(G,S)}(1_G,\ell ) \setminus \Phi _\prec )U_0]$ , respectively.
9 Reductions
In this section, we provide a set of reductions which exploit the combinatorial properties of independent sets and relate the results already obtained for hardcore models with other systems.
9.1 G-subshifts and conjugacies
Given a countable group G and a finite set $\Sigma $ endowed with the discrete topology, the full shift is the set $\Sigma ^G$ of maps $\omega : G \to \Sigma $ endowed with the product topology. We define the G-shift as the group action $G \times \Sigma ^G \to \Sigma ^G$ given by $(g,\omega ) \mapsto g \cdot \omega $ , where $(g \cdot \omega )(h) = \omega (hg)$ for all $h \in G$ . A G-subshift $\Omega $ is a G-invariant closed subset of $\Sigma ^G$ .
Given two G-subshifts $\Omega _1$ and $\Omega _2$ , we say that a map $\varphi : \Omega _1 \to \Omega _2$ is a conjugacy if it is bijective, continuous, and G-equivariant, that is, $g \cdot \varphi (x) = \varphi (g \cdot x)$ for every $\omega \in \Omega _1$ and $g \in G$ . In this context, these maps are characterized as sliding block codes (e.g., see [Reference Ceccherini-Silberstein and Coornaert12, Reference Lind and Marcus27]) and provide a notion of isomorphism between G-subshifts.
Any G-subshift $\Omega $ is characterized by the existence of a family of forbidden patterns $\mathfrak {F} \subseteq \bigcup _{F \in \mathcal {F}(G)} \Sigma ^F$ such that $\Omega = X_{\mathfrak {F}}$ , where
If the family $\mathfrak {F}$ can be chosen to be finite, we say that $\Omega $ is a G-subshift of finite type (G-SFT). Given a finite set $S \subseteq G$ , we can consider a family of $\lvert \Sigma \rvert \times \lvert \Sigma \rvert $ binary matrices $\mathbf {M} = \{M_s\}_{s \in S}$ with rows and columns indexed by the elements of $\Sigma $ , and define the set
The set $\Omega _{\mathbf {M}}$ is a special kind of G-SFT known as nearest neighbor (n.n.) G-SFT. It is known that for every G-SFT there exists a conjugacy to an n.n. G-SFT, so we are not losing much generality by considering n.n. G-SFTs instead of general G-SFTs.
We say that an n.n. G-SFT $\Omega _{\mathbf {M}}$ has a safe symbol if there exists $a \in \Sigma $ such that a can be adjacent to any other symbol $b \in \Sigma $ . Formally, this means that for all $s \in S$ and $b \in \Sigma $ , $M_s(a,b) = M_s(b,a) = 1$ .
9.2 Entropy and potentials
Given a G-subshift $\Omega $ , we define its topological entropy as
where $\{F_n\}_n$ is a Følner sequence and $\Omega _F = \{\omega _F: \omega \in \Omega \}$ is the set of restrictions of points in $\Omega $ to the set $F \subseteq G$ . It is known that the definition of $h_G(\Omega )$ is independent of the choice of Følner sequence and is also a conjugacy invariant, that is, if $\varphi : \Omega _1 \to \Omega _2$ is a conjugacy, then $h_G(\Omega _1) = h_G(\Omega _2)$ .
A potential is any continuous function $\phi : \Omega \to \mathbb {R}$ . Given a potential, we define the pressure as
where $Z_{F_n}(\phi ) = \sum _{w \in \Omega _F} \sup _{\omega \in [w]}\exp (\sum _{g \in F} \phi (g \cdot \omega ))$ . Notice that $p_G(0) = h_G(\Omega )$ .
A single-site potential is any potential that only depends on the value of $\omega $ at $1_G$ , that is, $\omega _{1_G}$ . In other words, and without risk of ambiguity, we can think that a single-site potential is just a function $\phi : \Sigma \to \mathbb {R}$ . In this case, $Z_{F_n}(\phi )$ has the following simpler expression:
In this context, we will say that a symbol $a \in \Sigma $ is a vacuum state if a is a safe symbol and $\phi (a) = 0$ .
9.3 From a hardcore model to an n.n. G-SFT with a vacuum state
Let $(\Gamma ,\unicode{x3bb} )$ be a hardcore model in $\mathcal {H}_G$ . If $G \curvearrowright \Gamma $ is transitive, then $\Gamma = \mathrm {Cay}(G,S)$ for some finite symmetric set $S \subseteq G$ . Then, it is easy to see that if $\Sigma = \{0,1\}$ and, for all $s \in S$ ,
then $\Omega _{\mathbf {M}}$ coincides with the set $X(\Gamma )$ and $0$ is a safe symbol. In addition, there is a natural relationship between the activity function $\unicode{x3bb} $ and the single-site potential given by $\phi (0) = 0$ and $\phi (1) = \log \unicode{x3bb} (v)$ , where v is some (or any) vertex v. In other words, if $G \curvearrowright \Gamma $ is transitive, then $(\Gamma ,\unicode{x3bb} )$ corresponds to an n.n. G-SFT with a vacuum state.
More generally, if $G \curvearrowright \Gamma $ is almost transitive, then $(\Gamma ,\unicode{x3bb} )$ can also be interpreted as an n.n. G-SFT with a vacuum state. Indeed, consider the set $\Sigma _\Gamma = X(\Gamma [U_0])$ , that is, the set of independent sets of the subgraph $\Gamma [U_0]$ induced by some fundamental domain $U_0$ . Since $\Gamma $ is locally finite and $G \curvearrowright \Gamma $ is free, there must exist a finite set $S \subseteq G \setminus \{1_G\}$ such that $SU_0$ contains all the vertices adjacent to $U_0$ . Considering this, we define a collection of matrices $\mathbf {M}_\Gamma = \{M_s\}_{s \in S}$ , where
and $xx'$ denotes the concatenation of the independent set x of $\Gamma [U_0]$ and the independent set $x'$ of $\Gamma [sU_0]$ . In other words, $M_s(x,x') = 1$ if and only if the union of the independent set x and the independent set $x'$ is also an independent set of $\Gamma [U_0 \cup sU_0]$ .
Then, there is a natural identification between $\Omega _{\mathbf {M}_\Gamma } \subseteq \Sigma _\Gamma ^G$ and $X(\Gamma )$ . In particular, the symbol $0^{U_0} \in X(\Gamma [U_0])$ plays the role of a safe symbol in $\Omega _{\mathbf {M}_\Gamma }$ . Moreover, we can define the single-site potential $\phi _\unicode{x3bb} : \Omega _{\mathbf { M}_\Gamma } \to \mathbb {R}$ given by $\phi _\unicode{x3bb} (\omega ) = \sum _{v \in U_0} \omega _{1_G}(v) \log \unicode{x3bb} (v)$ . Then, for every $F \in \mathcal {F}(G)$ ,
Therefore, $p_G(\Omega _\Gamma , \phi _\unicode{x3bb} ) = f_G(\Gamma ,\unicode{x3bb} )$ . In the language of dynamics, for every almost transitive and locally finite graph $\Gamma $ , there exists an n.n. G-SFT with a safe symbol $\Omega _\Gamma $ such that $G \curvearrowright X(\Gamma )$ and $G \curvearrowright \Omega _\Gamma $ are conjugated. Moreover, this gives us a way to identify any hardcore model $(\Gamma ,\unicode{x3bb} ) \in \mathcal {H}_G$ with the corresponding G-SFT $\Omega _\Gamma $ and the single-site potential $\phi _\unicode{x3bb} $ .
9.4 From an n.n. G-SFT with a vacuum state to a hardcore model
Conversely, given an n.n. G-SFT $\Omega $ and a potential with a vacuum state, we can translate this scenario into a hardcore model. Indeed, consider the graph $\Gamma _\Omega $ defined as follows:
-
• for every $g \in G$ , consider a finite graph $\Gamma _g$ isomorphic to $K_{\lvert \Sigma \rvert }$ , the complete graph with $\lvert \Sigma \rvert $ vertices. In other words, for each $g \in G$ and for each $a \in \Sigma $ , there will be a vertex $v_{g,a} \in V(\Gamma _g)$ and for every $a \neq b$ , the edge $(v_{g,a},v_{g,b})$ will belong to $E(\Gamma _g)$ ;
-
• the graph $\Gamma _\Omega $ will be the union of all the finite graphs $\Gamma _g$ plus some extra edges;
-
• for every $s \in S$ and $a,b \in \Sigma $ , we add the edge $(v_{1_G,a},v_{s,b})$ if and only if $M_s(a,b) = 0$ ;
-
• we define $\unicode{x3bb} _\phi : \Gamma _\Omega \to \mathbb {R}_{>0}$ as $\unicode{x3bb} _\phi (v_{g,a}) = \exp (\phi (a))$ for every $g \in G$ and $a \in \Sigma $ .
Then, G acts on $\Gamma _\Omega $ in the natural way and $V(\Gamma _{1_G})$ corresponds to a fundamental domain of the action $G \curvearrowright \Gamma _\Omega $ . In the language of dynamics, for every n.n. G-SFT with a safe symbol $\Omega $ , there exists an almost transitive and locally finite graph $\Gamma _\Omega $ such that $G \curvearrowright \Omega $ and $G \curvearrowright X(\Gamma _\Omega )$ are conjugated. Moreover, it is clear that
so in particular, all the representation and approximation theorems for free energy of hardcore models can be used to represent and approximate the pressure of n.n. G-SFTs $\Omega $ and potentials $\phi $ with a vacuum state, provided $(\Gamma _\Omega ,\unicode{x3bb} _\phi )$ satisfies the corresponding hypotheses. Relevant cases like the Widom–Rowlinson model [Reference Georgii, Häggström and Maes18] and graph homomorphisms from $\Gamma $ to any finite graph with some vertex (which plays the role of a safe symbol) connected to every other vertex fall into this category.
9.5 Topological entropy and constraintedness of n.n. G-SFTs with safe symbols
Let $\Omega \subseteq \Sigma ^G$ be an n.n. G-SFT with $\lvert \Sigma \rvert = n_s + n_u$ , where $n_s$ denotes the number of safe symbols in $\Sigma $ and $n_u$ denotes the number of symbols that are not safe symbols (unsafe). Consider the n.n. G-SFT $\Omega _{n_u} \subseteq \Sigma _{n_u}^G$ obtained after collapsing all the safe symbols in $\Sigma $ into a single one, so that the $\lvert \Sigma _{n_u} \rvert = 1 + n_u$ , and construct the graph $\Gamma _{\Omega _{n_u}}$ . Then, given $F \in \mathcal {F}(G)$ , we have that
so, considering that $n_u = \lvert U_0 \rvert = \lvert \Gamma _{\Omega _{n_u}} / G \rvert $ ,
Therefore, to understand and approximate $h_G(\Omega )$ reduces to study the hardcore model on $\Gamma _{\Omega ,n_s}$ with constant activity ${1}/{n_s}$ . In particular, if
the hardcore model $(\Gamma _{\Omega ,n_s},1/n_s)$ satisfies exponential SSM and the theory developed in the previous sections applies. This motivates the definition of the constraintedness of an n.n. G-SFT $\Omega $ as the connective constant of $\Gamma _{\Omega _{n_u}}$ , that is,
which can be regarded as a measure of how constrained is $\Omega $ (the higher $\mu (\Omega )$ , the more constrained it is). Notice that if
then $(\Gamma _{\Omega _{n_u}},1/n_s)$ satisfies exponential SSM. In particular, $\Omega _{n_u}$ has a unique measure of maximal entropy and therefore, $\Omega $ also has unique measure of maximal entropy, namely, the pushforward measure (see [Reference Burton and Steif11, Reference Häggström21]). Moreover, the topological entropy of $\Omega _{n_u}$ has an arboreal representation and can be approximated efficiently. Since $\mu (\Omega ) \leq \Delta (\Gamma _{\Omega _{n_u}}) - 1$ , we have that it suffices that
For example, the n.n. G-SFT $\Omega $ represented in Figure 6 satisfies that $\Delta (\Gamma _{\Omega _{n_u}}) = 6$ and $\unicode{x3bb} _c(6) = {5^5}/{4^6} = {3125}/{4096}$ ; then, if $n_s> {4096}/{3125} = 1.31072$ , we see that it suffices to have two copies of the safe symbol $0$ to have exponential SSM.
In general, since each vertex of the fundamental domain is connected to $n_u -1$ vertices in the clique and to at most $n_u$ vertices for each element s in the generating set S, we see that each vertex in $\Gamma _{\Omega _{n_u}}$ is connected to at most $(n_u - 1) + \lvert S \rvert n_u$ other vertices. Then, we can estimate that
so, in particular, if
exponential SSM holds (and therefore, again, uniqueness of measure of maximal entropy). This last equation and its relationship with the constraintedness of $\Omega $ has a similar flavor to the relationship between the percolation threshold $p_c(\mathbb {Z}^d)$ of the $\mathbb {Z}^d$ lattice and the concept of generosity for $\mathbb {Z}^d$ -SFTs introduced in [Reference Häggström21] by Häggström.
Remark 9.1. It may be the case that an n.n. G-SFT $\Omega \subseteq \Sigma ^G$ with a safe symbol could be represented by a graph $\Gamma $ which is better in terms of connectedness or maximum degree compared with the canonical representation $\Gamma _\Omega $ , since we could encode $\Sigma $ using other fundamental domains, with a lower connectivity than the complete graph. For example, the n.n. $\mathbb {Z}^2$ -SFT $\Omega _\Gamma $ corresponding to the graph $\Gamma $ on the left in Figure 7 has seven symbols (the seven independent sets of the $4$ -cycle), including a safe one. However, the canonical graph representation of $\Omega _\Gamma $ , that is, the graph $\Gamma _{\Omega _\Gamma }$ , has a fundamental domain consisting of a clique with six vertices, without considering extra connections. In particular, we see that both $\Gamma $ and $\Gamma _{\Omega _\Gamma }$ represent $\Omega $ , but $\Delta (\Gamma ) = 3 < 6 \leq \Delta (\Gamma _{\Omega _\Gamma })$ . This motivates a finer notion of constraintedness, namely,
and the aforementioned results would still hold if we replace $\mu (\Omega )$ by $\tilde {\mu }(\Omega )$ . Notice that a fundamental domain $U_0$ has at least $\lvert U_0\rvert +1$ independent sets (the empty one and all the singletons). In particular, this implies that $\tilde {\mu }(\Omega )$ is a minimum, since we only need to optimize over graphs $\Gamma $ with a fundamental domain $U_0$ such that $X(\Gamma [U_0]) = \lvert \Sigma _{n_u} \rvert $ .
9.6 The monomer–dimer model and line graphs
Given a graph $\Gamma = (V,E)$ , we say that two different edges $e_1,e_2 \in E$ are incident if they have one vertex in common. A matching in $\Gamma $ is a subset M of E without incident edges. In a total parallel with the hardcore model case, we can represent a matching with an indicator function $m: E \to \{0,1\}$ , denote the set of matchings of $\Gamma $ by $X^e(\Gamma )$ , and define the associated partition function for some activity function $\unicode{x3bb} : E \to \mathbb {R}_{> 0}$ as
The pair $(\Gamma ,\unicode{x3bb} )$ is called the monomer–dimer model and, as for the case of the hardcore model, we can define its associated free energy and Gibbs measures for a Gibbs specification adapted to this case.
An important feature of the monomer–dimer model is that, despite all its similarities with the hardcore model, it exhibits the SSM property for all values of $\unicode{x3bb} $ [Reference Bayati, Gamarnik, Katz, Nair and Tetali7] and, in particular, there is no phase transition [Reference Heilmann and Lieb22].
Considering this, most of the results presented in this paper, in particular those related to representation and approximation, can be adapted to counting matchings (see [Reference Gamarnik and Katz16] for a particular case), and there will not be a phase transition. One way to see this is through the line graph $L(\Gamma )$ of the given graph $\Gamma $ . Indeed, if we define $L(\Gamma )$ as the graph with the set of vertices E and the set of edges containing all the adjacent edges in E, it is direct to see that there is a correspondence between matchings in $\Gamma $ and independent sets in $L(\Gamma )$ , that is,
In particular, this tell us that all the results in our paper that involve some restriction on $\unicode{x3bb} $ apply to every graph that can be obtained as a line graph of another one without restriction on $\unicode{x3bb} $ . For example, the graph $\Gamma $ represented on the right in Figure 7 corresponds to the line graph of the Cayley graph of $\mathbb {Z}^2$ with canonical generators, that is,
Then, this observation implies that we can represent and approximate $f_{\mathbb {Z}^2}(\Gamma ,\unicode{x3bb} )$ for every $\mathbb {Z}^2$ -invariant activity function $\unicode{x3bb} $ on $\Gamma $ .
9.7 From almost free to free
Suppose that $G \curvearrowright \Gamma _*$ is almost free, that is, $\lvert \mathrm {Stab}_G(v) \rvert < \infty $ for all v. We proceed to show how to reduce the computation of $f_G(\Gamma ,\unicode{x3bb} )$ to the computation of $f_G(\Gamma _*,\unicode{x3bb} _*)$ for some free action $G \curvearrowright \Gamma _*$ , where $\Gamma _*$ and $\unicode{x3bb} _*$ are some suitable auxiliary graph and activity function, respectively. We consider this as another example of the versatility of independent sets for representing many phenomena.
Given a graph $\Gamma $ and an almost free action $G \curvearrowright \Gamma $ , let $\Gamma _*$ be the new graph obtained by setting
and
In simple words, for each v in $V(\Gamma )$ , there are $\lvert \mathrm {Stab}_G(v) \rvert $ copies of v in $V(\Gamma _*)$ such that:
-
(1) the $\lvert \mathrm {Stab}_G(v) \rvert $ copies of v form a clique in $\Gamma _*$ ;
-
(2) for $(v,v') \in E(\Gamma )$ , each copy of v is connected to all copies of $v'$ in $\Gamma _*$ .
Next, consider the activity function $\unicode{x3bb} _*: V(\Gamma _*) \to \mathbb {R}_{>0}$ given by
Notice that for every $U \Subset V(\Gamma )$ , we have that
where $U_* \Subset V(\Gamma _*)$ denotes the set of all copies of vertices in U. Indeed, notice that each independent set in $\Gamma _*[U_*]$ can be naturally identified with a unique independent set in $\Gamma [U]$ : for $x' \in X(\Gamma _*)$ , we can define $x \in X(\Gamma )$ as $x(v) = 1$ if and only if there exists $s \in \mathrm {Stab}_G(v)$ so that $x'((v,s)) = 1$ . Conversely, if $\Gamma $ is finite, each independent set $x \in X(\Gamma )$ can be identified with $\prod _{v \in \Gamma } \lvert \mathrm {Stab}_G(v) \rvert ^{x(v)}$ copies in $X(\Gamma _*)$ . Therefore,
Now, pick a fundamental domain $U_0 \subseteq V$ of $G \curvearrowright \Gamma $ and, for each $v \in U_0$ , consider the set of left cosets $\{g\mathrm {Stab}_G(v): g \in G\}$ with a fixed set of representatives $R(v)$ , that is, $G = \bigsqcup _{g \in R(v)} g\mathrm {Stab}_G(v)$ for each $v \in U_0$ . Without loss of generality, $1_G \in R(v)$ for every v. Next, given $v \in U_0$ and $h \in G$ , define $t_{v,h}$ as the unique element in $\mathrm {Stab}_G(v)$ such that $ht_{v,h}^{-1} \in R(v)$ . In addition, given another element $r \in G$ , define $\psi ^v_{h \to r} := ht_{v,h}^{-1}t_{v,r}h^{-1}$ . Notice that if $t \in \mathrm {Stab}_G(v)$ , then $t_{v,ht} = t_{v,h} t$ and $\psi ^v_{ht \to rt} = \psi ^v_{h \to r}$ . Next, consider the action of G on $\Gamma _*$ that, given a vertex $(u,s) \in V(\Gamma _*)$ and $h \in G$ , it is defined as
where $u \in Gv$ for $v \in U_0$ and g is some (or any) element in G such that $u = gv$ . First, let us check that this is indeed an action. If $v \in U_0$ , then
Therefore, if $(u,s)$ is arbitrary, with $u = gv$ and $s = gtg^{-1}$ for $g \in R(v)$ and $t \in \mathrm {Stab}_G(v)$ , we have that
Now, let us check that the action is free. If $h \cdot (v,1_G) = (v,1_G)$ for $v \in U_0$ , then $(hv, ht_{v,h}h^{-1}) = (v,1_G)$ , so $h \in \mathrm {Stab}_G(v)$ and $t_{v,h} = 1_G$ . Therefore, $h = 1_G$ . In the general case, if $h \cdot (gv,s) = (gv,s)$ with $u = gv$ and $s = gtg^{-1}$ for $g \in R(v)$ and $t \in \mathrm {Stab}_G(v)$ , we have that $(hgt) \cdot (v, 1_G) = h \cdot ((gt) \cdot (v,1_G)) = (gt) \cdot (v,1_G)$ , so $(t^{-1}g^{-1}hgt) \cdot (v,1_G) = (v,1_G)$ and, by the previous step, $t^{-1}g^{-1}hgt = 1_G$ or, equivalently, $h = 1_G$ .
Now, if $G \curvearrowright \Gamma $ is almost transitive, then $G \curvearrowright \Gamma _*$ is almost transitive, too, with $\lvert \Gamma _*/G \rvert = \lvert \Gamma /G \rvert $ . Indeed, if $U_0$ is a fundamental domain for $G \curvearrowright \Gamma $ , we have that $U_0 \times \{1_G\}$ is a fundamental domain for $G \curvearrowright \Gamma _*$ , since for every $(u,s) \in V(\Gamma _*)$ , there exists a unique $v \in U_0$ , $g \in G$ , and $t \in \mathrm {Stab}_G(v)$ such that $u = gv$ and $s = gtg^{-1}$ , so $(gt) \cdot (v,1_G) = (u,s)$ .
Finally, if $K = \bigcup _{v \in U_0} \mathrm {Stab}_G(v)$ , observe that $U_0 \times \{1_G\} \subseteq (U_0)_* \subseteq K (U_0 \times \{1_G\})$ , so
and, since $Z_\Gamma (F_nU_0,\unicode{x3bb} ) = Z_{\Gamma _*}((F_nU_0)_*,\unicode{x3bb} _*) = Z_{\Gamma _*}(F_n(U_0)_*,\unicode{x3bb} _*)$ , applying logarithms, dividing by $\lvert F_nU_0 \rvert $ , and taking the limit in n, we obtain that
where we have used that $\{F_nK\}_n$ is a Følner sequence, $\lim _n {\lvert F_nK \rvert }/{\lvert F_n \rvert } = 1$ , and $\lvert F_n(U_0 \times \{1_G\}) \rvert = \lvert F_nU_0 \rvert = \lvert F_n \rvert \lvert U_0 \rvert $ .
9.8 Spectral radius of matrices and occupation probabilities on trees
A curious consequence of the hardcore model representation of an n.n. G-SFT with a safe symbol is that when $G = \mathbb {Z}$ and $S = \{1\}$ , then $h_{\mathbb {Z}}(\Omega )$ has a well-known characterization in terms of the transition matrix $M = M_1$ [Reference Lind and Marcus27].
If M is irreducible and aperiodic, there is always a unique stationary Markov chain $\mathbb {P}_M$ associated to M such that $\log \unicode{x3bb} _M = h_{\mathbb {Z}}(\Omega _M)$ , where $\unicode{x3bb} _M$ denotes the Perron eigenvalue of M and we consider the natural invariant order in $\mathbb {Z}$ .
Now, if M is a matrix such that the ith row and the ith column have no zeros, then M is irreducible and aperiodic. In fact, the ith symbol, let us call it a, is a safe symbol. In this case, we have that
Therefore, $\unicode{x3bb} _M = {1}/{\mathbb {P}_M(a^{0} \vert a^{-1})}$ and to compute the spectral radius of M reduces to compute $\mathbb {P}_M(a^{0} \vert a^{-1})$ . For example, consider the following matrix:
where a is the symbol associated to the first row. Given this matrix M, we can always construct a graph representation $\Gamma _{\Omega _M}$ of $\Omega _M$ as in Figure 8.
Now, it is known that $\lvert \mathbb {P}_M(0^{0} \vert 0^{-1}) - \mathbb {P}_M(0^{0} \vert 0^{\{n,-1\}}) \rvert $ goes to zero exponentially fast as n goes to infinity and, since every Markov chain is a Markov random field, we have that
This gives us an arboreal representation and a method to compute the spectral radius of any matrix M satisfying the conditions described above that we believe could be of independent interest.
Acknowledgements
I would like to thank Brian Marcus for his valuable suggestions after reading a first draft of this work, Tom Meyerovitch for a helpful discussion about invariant random orders, and the anonymous referee for a careful reading of the manuscript and many useful comments and suggestions. I acknowledge the support of ANID/FONDECYT de Iniciación en Investigación 11200892.