Zero-free regions of partition functions with applications to algorithms and graph limits

Introduction

In a series of papers Barvinok and Barvinok and Soberón developed a technique that yields quasi-polynomial time approximation schemes for several hard counting problems such as computing the permanent of a matrix and computing the number of (edge-colored) graph homomorphisms into a fixed graph. Their technique is essentially based on two things. First the counting problem is cast as the evaluation of some polynomial and they identify a region where this polynomial is nonzero. Secondly, they prove that in this zero-free region the logarithm of the polynomial is well-approximated by a low order Taylor approximation, which they prove to be computable in quasi-polynomial time.

In this paper we will apply this method to partition functions of edge-coloring models and more generally to Holant counting problems and contractions of tensor networks. That is, fixing a degree bound $\Delta$, we will identify edge-coloring models for which the partition function does not vanish on graphs with maximum degree at most $\Delta$ and consequently show how to approximately compute the partition function in quasi-polynomial time. We moreover show that the normalised logarithm of the partition function is continuous with respect to the Benjamini-Schramm topology for these models, and we give give quasi-polynomial time algorithms for approximately evaluating a large class of graph polynomials, including the Tutte polynomial and the matching polynomial, on bounded degree graphs.

Below we will introduce and describe these concepts in a bit more detail and state our results.

If $a$ is the all-ones vector and $B$ is the adjacency matrix of some graph $H$, then $p(G)(a,B)$ is equal to the number of graph homomorphisms from $G$ to $H$.

Partition functions of edge-coloring models include partition function of vertex-coloring models, as has been shown by Szegedy , cf. Lemma 5 in Section 2.1. But they form a much bigger class of graph invariants, cf. . For example, the number of matchings is not equal to the partition function of any vertex-coloring model. Partition functions of edge-coloring models have been characterised in and based on invariant theory of the orthogonal group and the Nullstellensatz.

In many cases it is NP-hard to determine whether or not the partition function of an edge- or vertex-coloring model vanishes on general graphs. However, when restricted to bounded degree graphs things may become easier. In particular, Barvinok and Soberón proved that when $a$ is the all ones vector and $B$ is sufficiently close to the all ones matrix, then

Based on the technique of Barvinok and Barvinok and Soberón we will prove in Section 3 a similar result for partition functions of edge-coloring models:

In fact, we will state and prove in Section 3 a slightly more general version of Theorem 1 that also applies to tensor networks. The definition of tensor networks will be given in Section 2.

While every partition function of a vertex-coloring model is equal to the partition function of some edge-coloring model, the exact relation between Theorem 1 and (3) is presently not clear. It is possible though to derive a qualitative version of (3) from Theorem 1 (even valid for vertex vertex-coloring models with vertex weights close to $1$). We will however not do this here. Instead, in Section 3 we will present an example of a vertex-coloring model to which the result of Barvinok and Soberón does not apply, while from our results it follows that its partition function does not evaluate to zero on bounded degree graphs, cf. Example 2.

2 Computing partition functions

Exact computation Computing partition functions is in many cases $\#$P-hard. There is a line of work by Dyer and Greenhill , Bulatov and Grohe , Cai, Chen and Lu , where dichotomy theorems have been proved for the complexity of computing partition functions of vertex-coloring models. Roughly they proved that if the model has a very special structure, its partition function can be computed in polynomial time and it is $\#$P-hard to compute otherwise. In a sequence of papers Cai Lu and Xia , Cai, Huang and Li , and Cai, Guo and Williams have proved similar results for partition functions of edge-coloring models with $2$ colors. In fact, in these papers they consider Holant counting problems, but they include partition functions of edge-coloring models. These Holant counting problems may be seen as tensor network contractions and we will define these in Section 2.2. Approximate computation Since computing partition functions is in many case $\#$P-hard, people have started looking at approximation algorithms. Let us consider the case of counting weighted independent sets. For a graph $G$ and $\lambda>0$, denote by $p_{\lambda}(G)$ the sum over all independent sets of $G$, where an independent set $I$ is counted with weight $\lambda^{|I|}$. Note that p_{{\color[rgb]{0,0,0}\lambda}}(G) may be viewed as the partition function of a=({\color[rgb]{0,0,0}\lambda},1) and B=\left(\begin{array}[]{cc}0&1\\ 1&1\end{array}\right). A surprising threshold phenomenon has been found for the complexity of approximating $p_{\lambda}(G)$: for $\lambda<\lambda_{c}(\Delta):=(\Delta-1)^{\Delta-1}/(\Delta-2)^{\Delta}$ there exists a fully-polynomial time approximation scheme (FPTAS) for graphs of maximum degree at most $\Delta$, discovered by Weitz ; for $\lambda>\lambda_{c}$ there does not exist a fully-polynomial time randomised approximation scheme (FPRAS) for $\Delta$-regular graphs (with $\Delta\geq 3$), unless NP=RP, as has been proved by Sly and Sun . The threshold $\lambda_{c}$ is the critical point for the (infinite) $\Delta$-regular tree to have a unique Gibbs measure. This phenomenon suggests an intimate connection between phase transitions in statistical physics and computational complexity. The ideas of Weitz have been applied and extended to other types of counting problems and partition functions; see e.g. . Other interesting approximation algorithms and hardness results have been found for partition functions of vertex-coloring models an planar graphs . Our contribution In Section 4 of this paper we apply Theorem 1 to obtain a quasi-polynomial time approximation scheme (QPTAS) for the computation of partition functions of a large class of edge-coloring models on bounded degree graphs, based on a technique developed by Barvinok . This technique was used by Barvinok and Soberón to obtain a QPTAS for the computation of partition function of vertex-coloring models on bounded degree graphs (with $a$ equal to the all ones vector).

The main idea is to rewrite the partition function as the evaluation of a univariate polynomial $q$ at $1$ and then use a low order Taylor approximation to $\ln q$. The approximation turns out to be good when the roots of $q$ have absolute value at least $M$ for some fixed constant $M>1$. Theorem 1 is used to guarantee the existence of this constant $M$. From the perspective of the Lee-Yang approach to phase transition in statistical physics , one may view zero-free regions of the partition function as regions far away from a phase transition. So this approach also indicates a connection between statistical physics and computational complexity.

We need one definition to state our result.

We prove the following result in Section 4:

Theorem 2 also applies to contractions of tensor networks and Holant counting problems. See Section 4 for the exact details.

3 Evaluating graph polynomials

It turns out that the technique of Barvinok can also be applied to graph polynomials of exponential type. This is a class of graph polynomials introduced by Csikvári and Frenkel , which includes many important polynomials such as the Tutte polynomial, the matching polynomial and many more. We will define these polynomials in Section 4.3, where we obtain a QPTAS for computing certain evaluations of these polynomials on bounded degree graphs, cf. Theorem 14. Let us for now specialise these results to the Tutte polynomial.

For a graph $G=(V,E)$ the random cluster model formulation of the Tutte polynomial Z(G)({\color[rgb]{0,0,0}q},v), is defined as follows:

where $k(A)$ denotes the number of connected components of the graph $(V,A)$. We will consider the Tutte polynomial for fixed $v$ as a polynomial in {\color[rgb]{0,0,0}q}.

In Goldberg and Jerrum showed that approximating Z(G)({\color[rgb]{0,0,0}q},v) for general graphs and for {\color[rgb]{0,0,0}q}>2 and $v>0$ is as hard as counting independent sets in bipartite graphs (#BIS). The present results may be an indication that this is not the case for bounded degree graphs. See for related algorithmic results for the Potts model and for hardness results for the Potts model on bounded degree graphs.

4 Sparse graph limits

In 2001, Benjamini and Schramm defined a convergence notion for finite bounded degree planar graphs, which can also be extended to general bounded degree graphs and is often referred to as Benjamini-Schramm convergence, local convergence or weak convergence. This convergence notion has many equivalent definitions (see the book by Lovász [29, Proposition 5.6]) and we choose one which is most suitable for our purposes. Fix a degree bound $\Delta$ and let $(G_{n})$ be a sequence of simple graphs, each of maximum degree at most $\Delta$. We call the sequence $(G_{n})$ locally convergent if $|V(G_{n})|$ goes to infinity, as $n\to\infty$ and if for each connected simple graph $H$ the quantity

is a convergent sequence of real numbers, where in (5) $\text{ind}(H,G_{n})$ denotes the number of induced subgraphs of $G_{n}$ that are isomorphic to $H$. As an example let $C_{n}$ be the cycle of length $n$. Then $(C_{n})$ is locally convergent. See for possible representations of limit objects.

where $G$ is a graph. This normalisation is motivated by statistical physics, where this quantity is known as the entropy per vertex. Note from the perspective of estimability it does not matter to take the absolute value of $p(G)(h)$ before applying the logarithm. For if we fix a some branch of the (complex) logarithm, then the imaginary part is bounded, and dividing it by $|V(G_{n})|$ will make it disappear in the limit.

Borgs, Chayes, Kahn and Lovász showed that if one in (6) replaces $p(G)(h)$ by $p(G)(a,B)$ for appropriate $(a,B)$ this parameter is estimable; see also . In Csikvári and Frenkel showed that if one replaces $p(G)(h)$ by $q(G)(z)$ in (6), where $q$ is a graph polynomial of bounded exponential type and $|z|$ is large enough, then this parameter is estimable. This extends work of Abért and Hubai who showed that this holds for the chromatic polynomial.

Utilising Theorem 1 and building on a result of Csikvári and Frenkel , we will prove that the normalised partition function of an edge-coloring model that is sufficiently close to the all ones edge-coloring model is also estimable.

5 Organisation of the paper

In the next section we collect some preliminaries and set up some notation. In particular, we introduce tensor networks. In Section 3 we will prove a slight generalisation of Theorem 1 valid for tensor networks. In Section 4 we will discuss the technique of Barvinok mentioned earlier and prove Theorems 2 and 3. In Section 5 we will give a proof of Theorem 4. Finally, in Section 6 we will conclude with a few remarks. Sections 4 and 5 may be read independently of each other.

Preliminaries

We will setup some basic notation and give some definitions here that are used throughout the paper.

Whenever we talk about an edge-coloring model we will always assume it has $k$ colors, where $k$ is some fixed natural number. In particular, in algorithmic statements we will consider $k$ as a constant and moreover assume that it is at least $2$, for else computing the partition function is trivial.

2 Tensor networks

As mentioned in the introduction, Theorem 1 not only applies to edge-coloring models but also to tensor networks. We will introduce tensor networks here.

Let $h=(h^{v})_{v\in V}\in S_{G}$. We call the pair $(G,h)$ a tensor network. The contraction of the tensor network $(G,h)$ is defined as follows:

Contractions of tensor networks have been used to simulate quantum computing by Markov and Shi in , where they gave a polynomial time algorithm for contracting tensor networks on bounded degree graphs of bounded treewidth. In Arad and Landau use quantum algorithms to compute additive approximations to tensor network contractions. We refer to both and and the references in there for more details concerning the connection of tensor networks and quantum information theory. Contractions of tensor networks can also be used to model Holant counting problems (see ).

3 The orthogonal group

For edge-coloring models this is proved in and the same proof also works for contractions of tensor networks.

Absence of roots for tensor network contractions

Let $G=(V,E)$ be a graph and let $\eta\in(0,\infty)$. For any $\theta\in(0,2\pi/3)$ fix $\beta\leq\eta\theta\cos(\theta/2)$ and let $\delta:=\min\{\eta,\frac{\beta}{\Delta(G)+1}\}$. Then for each $h\in S_{G}(\delta,\eta)$, $|p(G)(h)|\geq(\cos(\theta/2)\eta)^{|V|}k^{|E|}$. In particular, $p(G)(h)\neq 0$.

We will prove Theorem 6 in the next section, but we will first state some consequence.

Then $0.71885\approx\beta^{*}(1)<\beta^{*}(2)<\beta^{*}(3)<\cdots\leq x^{*}\approx 1.12219$. We have the following corollary, which implies Theorem 1.

Let us first consider the case where $a_{v}=1$ for all $v$. Let $\eta:=1-\frac{\beta^{*}}{2\Delta(G)+2}$. A simple computation shows that {\color[rgb]{0,0,0}\beta^{*}=\eta x^{*}}. Clearly, $\eta>\beta^{*}/2$. So if we let $\delta=\frac{\beta^{*}}{\Delta(G)+1}$, then each $h^{v}\in S(\delta,\eta)$ and hence (10), with $a_{v}=1$ for each $v\in V$, follows from Theorem 6.

In the general case let $g^{v}(\alpha)=h^{v}(\alpha)/a_{v}$ for each $\alpha$ and $v\in V$. Then for each $v$ and $\alpha$, $|1-g^{v}(\alpha)|\leq\frac{\beta^{*}}{2(\Delta(G)+1)}$. So (10), with $a_{v}=1$ for each $v\in V$, holds for $p(G)(g)$. Since $p(G)(h)=\prod_{v\in V}{a_{v}}\cdot p(G)(g)$, (10) now follows. ∎

Corollary 6b is roughly saying that if the tensors $h^{v}$ are close enough to the rank one tensor $h_{x}$, then the tensor network contraction is not equal to zero.

We will now give an example illustrating the power and weakness of our results.

For $\mu=1$ we can view $p(h_{U})(G)$ as a polynomial in $\lambda$, which for $\Delta$-regular graphs coincides with the independence polynomial of $G$ evaluated at $\lambda^{\Delta}$. Scott and Sokal proved that, if $|\lambda^{\Delta}|\leq\frac{(\Delta-1)^{\Delta-1}}{\Delta^{\Delta}}$, then $p(h_{U})(G)\neq 0$ on any $\Delta$-regular graph $G$. They moreover showed that this bound is tight. As $\Delta\to\infty$ this bound behaves roughly like $\frac{1}{e\Delta}$, while the result we obtain is of the order $O(\frac{1}{\Delta^{\Delta}})$, showing that our results are not optimal.

Our proof of Theorem 6 is based on a method of Barvinok and Barvinok and Soberón . Following Barvinok we can say that although the method of proof is similar to the methods considered in it does require some effort and new ideas.

We will first state and prove several lemmas. The first lemma about angles between vectors is due to Boris Bukh see . We refer to for a proof.

For $F\subseteq E$ and $\phi:F\to[k]$ define

So $p^{F}_{\phi}(G)$ is a polynomial and we can evaluate this at $h\in S_{G}$. In particular, if $F=\emptyset$, then $p^{F}_{\phi}(G)(h)$ just coincides with the ordinary tensor network contraction $p(G)(h)$.

In the two lemmas below we assume that we have fixed some graph $G=(V,E)$ and $\eta,\delta>0$. Moreover, for $u\in V$ we let $\delta(u)\subseteq E$ be the set of edges incident with $u$ and $N(u)\subset V$ the set of neighbours of $u$.

Let $\tau>0$, let $F\subseteq E$, let $\phi:F\to[k]$ and let $u\in V$. If for all $h\in S_{G}(\delta,\eta)$ and for each $\psi:F\cup\delta(u)\to[k]$ extending $\phi$ we have $p^{F\cup\delta(u)}_{\psi}(G)(h)\neq 0$ and moreover for each $v\in N(u)\cup\{u\}$:

then the angle of $p^{F\cup\delta(u)}_{\psi^{\prime}}(G)(h)$ and $p^{F\cup\delta(u)}_{\psi}(G)(h)$ for any $\psi,\psi^{\prime}:F\cup\delta(u)\to[k]$ extending $\phi$ is at most

Note that (14) equals zero if $\alpha$ is not $v$-compatible with $\psi$. Then for each $h\in S_{G}(\delta,\eta)$ we obtain by (12) that

Let $\theta\in[0,2\pi/3)$. Let $u\in V$ and let $F\subseteq E$ with $\delta(u)\subseteq F$. Let $\phi:F\to[k]$. Suppose that for each $v\in N(u)\cup\{u\}$, all $h\in S_{G}(\delta,\eta)$ and all maps $\psi,\psi^{\prime}:F\cup\delta(v)\to[k]$ extending $\phi$, we have $p^{F\cup\delta(v)}_{\psi}(G)(h)\neq 0$ and that the angle between $p^{F\cup\delta(v)}_{\psi}(G)(h)$ and $p^{F\cup\delta(v)}_{\psi^{\prime}}(G)(h)$ is at most $\theta$. Then for each $v\in N(u)\cup\{u\}$ and all $h\in S_{G}(\delta,\eta)$ we have

we obtain that for any $h\in S_{G}(\delta,\eta)$,

where the first inequality in (18) is due to Lemma 7, since by assumption for each $\psi,\psi^{\prime}$ and any $h\in S_{G}(\delta,\eta)$ we have that the angles between $p^{F\cup\delta(v)}_{\psi}(G)(h)$ and $p^{F\cup\delta(v)}_{\psi^{\prime}}(G)(h)$ differ by no more than $\theta$, the second inequality is obvious and the equality in (18) is due to (17). This proves the lemma. ∎

Fix a graph $G=(V,E)$ and $h\in S_{G}(\delta,\eta)$. If we plug in $\tau=\cos(\theta/2)$ in (13), then by assumption we have that (13) is at most $\theta$. We will first show that the following three statements hold:

Note that (19) (i) for $F=\emptyset$ already implies that $p(G)(h)\neq 0$ for all $h\in S_{G}(\delta,\eta)$.

We will now prove that (19) (i), (ii) and (iii) hold for all sets $F\subseteq E$ by induction on $|E\setminus F|$. If $F=E$, then (i) holds since $p^{E}_{\phi}(G)(h)$ is just the product of $|V|$ nonzero numbers. Clearly, (ii) also holds. Moreover, (iii) also holds since for each $v$,

and the sum in this equation consists of only one term.

Let now $F$ be a subset of $E$ of size strictly smaller than $E$. Let $u\in V$. If $\delta(u)\subseteq F$, then (ii) is clearly true. So we may assume that \delta(u){\color[rgb]{0,0,0}\nsubseteq}F. Let $\phi:F\to[k]$ and let $\psi,\psi^{\prime}:F\cup\delta(u)\to[k]$ be maps that extend $\phi$. Then by induction from (i) and (iii) (since $|F\cup\delta(u)|>|F|$) we know that the conditions of Lemma 8 are satisfied with $\tau=\cos(\theta/2)$. This implies that (ii) holds for the set $F$.

To prove that (i) holds for $F$, fix $v$ such that \delta(v){\color[rgb]{0,0,0}\nsubseteq}F. Then

As by induction the $p^{F\cup\delta(v)}_{\psi}(G)(h)$ are nonzero and by (ii) we know that their angles differ by at most $\theta$, Lemma 7 implies that $p^{F}_{\phi}(G)(h)$ is nonzero for any $h\in S_{G}(\delta,\eta)$.

Finally, take $u$ such that $\delta(u)\subseteq F$. If no such $u$ exists there is nothing to prove for (iii). Fix $v\in N(u)\cup\{u\}$. Since the sum in (16) has only one contributing factor if $\delta(v)\subseteq F$, we may assume that \delta(v){\color[rgb]{0,0,0}\nsubseteq}F. By induction, from (ii) we know that the angle between $p^{F\cup\delta(v)}_{\psi}(G)(h)$ and $p^{F\cup\delta(v)}_{\psi^{\prime}}(G)(h)$ for any $\psi,\psi^{\prime}:F\cup\delta(v)\to[k]$ extending $\phi$ is at most $\theta$, as $|F\cup\delta(v)|>|F|$. So Lemma 9 implies that (iii) holds for $F$. So by induction we conclude that (19) holds for all sets $F$.

To finish the proof write $V=\{v_{1},\ldots,v_{n}\}$ and let $F_{0}=\emptyset$. For $i>0$ let $F_{i}:=F_{i-1}\cup\delta(v_{i})$. We claim that for each $i=0,\ldots,n$, $\phi:F_{i}\to[k]$ and $h\in S_{G}(\delta,\eta)$ we have

Indeed, for $i=n$ this is clearly true. Next, pick any $i<n$ and $\phi:F_{i}\to[k]$. Then

where the first inequality follows from (19) (ii), and the second by induction. This shows (20) and finishes the proof. ∎

Approximation algorithms

In this section we will consider algorithms for computing tensor network contractions and evaluations of graph polynomials. Both algorithms are based on a method of Barvinok (which has also been used by Barvinok and Barvinok and Soberón ), which we describe first.

Note that (22) only depends on the values of $\frac{d^{m}}{dt^{m}}p|_{t=0}$ for $m=0,\ldots,n$. (Where we agree that the $0^{\text{th}}$ derivative is just the function itself.) To see this note that $f^{\prime}(z)=p^{\prime}(z)/p(z)$, that is, $p^{\prime}(z)=p(z)f^{\prime}(z)$. So for $m\geq 1$ we have

This implies that if we can compute the values of $\frac{d^{j}}{dz^{j}}p(z)|_{z=0}$ for $j=0,\ldots,n$, then (23) provides a nondegenerate (as $p(0)\neq 0$) triangular system of equations to compute $\frac{d^{j}}{dz^{j}}f(z)|_{z=0}$ for $j=1,\ldots,n$, which can be done in time $n^{O(1)}$. To summarise:

If the values \frac{d^{m}}{dz^{m}}{\color[rgb]{0,0,0}p}|_{z=0} are given for $m=0,\ldots,n$, then $\frac{d^{m}}{dz^{m}}f|_{z=0}$ can be computed in time $n^{O(1)}$ for each $m=0,\ldots,n$.

The quality of the approximation (22) depends on the complex roots of $p$.

The proof of (26) is quite similar to the proof of Lemma 1.2 from , but for completeness we will give it here.

for any $z$ such that $|z|\leq|t|$. Using the standard Taylor expansion for the principal branch of the logarithm, we obtain

(26) now follows by combining (28) with (29) and using the bound on $|R_{n}|$.

Take $n=C(\ln d/\varepsilon)$ (where C\geq(\ln{\color[rgb]{0,0,0}1/}q)^{-1} is large enough so that $1/n\leq 1-q$). Then the right-hand side of (26) is at most $\varepsilon$. Write $z=T_{n}(f)(t)$. Then we have $|e^{f(t)-z}|=|e^{f(t)-z}|\leq e^{|f(t)-z|}\leq e^{\varepsilon}$ and similarly $|e^{-z+f(t)}|\leq e^{\varepsilon}$. (This follows form the fact that for a complex number $y=a+bi$, we have $|e^{y}|=e^{a}$ and $|a|\leq|y|$.) Moreover, the angle between $e^{z}$ and $e^{f(t)}$ is bounded by $|\Im\ln e^{z-f(t)}|\leq|\ln e^{z-f(t)}|\leq\varepsilon$. This shows (25).

To see (24), take $n=O(\ln 1/\varepsilon)$ such that the right-hand side of (26) at most $d\varepsilon$. Then we have $|e^{z}|\leq|e^{f(t)}|e^{d\varepsilon}$ and |e^{f(t)}|\leq|e^{{\color[rgb]{0,0,0}z}}|e^{d\varepsilon}, which is equivalent to (24). ∎

2 Approximating tensor network contractions

In this section we will combine Theorem 6 with Lemmas 10 and 11 to give a quasi-polynomial time algorithm for the computation of tensor network contractions for a large class of tensor networks. In particular, Theorem 2 will be proved here.

Consider a graph $G=(V,E)$ and $h\in S_{G}$. Suppose that $h$ satisfies

Note that $q(1)=p(G)(h)$. So we are interested in computing the value of $q$ at $z=1$. By Corollary 6a we have that for any $|z|\leq 1.01$, $q(z)\neq 0$. So by Lemma 11 we can compute a fast $\varepsilon$-approximation to $p(G)(h)$ provided we can compute the $m$th derivative of $q$ at $z=0$ efficiently. This can be done in time $|V|^{O(m)}$ for each $m$. Indeed, for any $m$,

Let us denote by $E(U)$ the edges in $E$ that are incident with some vertex of $U$ for $U\subseteq V$. Then (32) is equal to

and hence can be computed in time $|V|^{m}k^{m\Delta(G)}=|V|^{O(m)}$. By Lemmas 10 and 11, we have the following result, which clearly implies Theorem 2.

Theorem 12 of course also applies to tensor networks that strictly satisfy the conditions of Corollaries 6a and b, but we leave the details to the reader.

3 Approximating evaluations of graph polynomials

In this section we will combine a result of Csikvári and Frenkel with Lemma 10 and Lemma 11 to give a quasi-polynomial approximation scheme for evaluating a large class of graph polynomials, including the Tutte polynomial.

(here $G[V_{i}]$ is the subgraph of $G$ induced by $V_{i}$). So $\chi(G)$ is a polynomial of degree at most $|V|$ with zero constant term and the coefficient of $z$ is equal to $\chi(G)$. If $\chi(K_{1})\neq 0$, then the degree of $p_{\chi}$ is equal to $|V|$. Csikvári and Frenkel call graph polynomials that arise this way graph polynomials of exponential type. (In fact, they give a different definition, but show that the definition above is equivalent to it.)

Csikvári and Frenkel proved that these polynomials have bounded roots on $\mathcal{G}_{\Delta}$:

Let us write $n:=|V|$ and define for $k=0,1,\ldots,n$, $\mathcal{P}_{k}$ to be the set of partitions of $V$ into exactly $k$ nonempty sets. Then

For $m\neq n-k$ the contribution will be zero. So (35) is equal to

No more than $m$ sets in $\mathcal{P}_{n-m}$ can have size greater than or equal to $2$. So to enumerate $\mathcal{P}_{n-m}$, we first select a set of $n-2m$ vertices and then find all partitions into exactly $m$ sets of the remaining $2m$ vertices. This gives a total of $n^{O(m)}$ steps. Since $\chi$ is efficient, the sum (36) can be computed in time $n^{O(m)}$.

Let now $t=1/x$. Then $|t|<\frac{1}{c\kappa}$. Lemmas 10 and 11 then imply that we can compute numbers $\xi_{1}$ in time $n^{O(\ln(n/\varepsilon))}$ such that $e^{-\varepsilon}\leq|\frac{\xi_{1}}{q(t)}|\leq e^{\varepsilon}$ and such that the angle between $\xi_{1}$ and $q(t)$ is at most $\varepsilon$, and $\xi_{2}$ in time $n^{O(1/\varepsilon)}$ such that $\big|\ln|q(t)|-\xi_{2}\big|\leq\varepsilon n$. Then $\alpha_{1}:=x^{n}\xi_{1}$ is a multiplicative $\varepsilon$-approximation to $p_{\chi}(x)$ and $\alpha_{2}:=\xi_{2}+n\ln|x|$ is an additive $\varepsilon n$-approximation to $\ln|p_{\chi}(x)|$. This finishes the proof. ∎

Sparse graph limits and edge-coloring models

In this section we will prove Theorem 4. To do this we will use the framework of Csikvári and Frenkel .

Recall that $\beta^{*}(\Delta+1)\geq\beta^{*}(1)\approx 0.71885$; see Section 3. Now fix some small constant $\delta>0$ and fix $h\in\mathcal{E}(\Delta,\delta)$. Consider the following two graph polynomials:

Observe that $q(G)(1)=p(G)(h)=k^{|E(G)|}\hat{q}(G)(1)$ and that $\hat{q}$ is monic.

For a graph $G$ we define $\mu_{G}$ to be the uniform distribution on the roots of $\hat{q}(G)$. Note that for all graphs $G\in\mathcal{G}_{\Delta}$ the measures $\mu_{G}$ are all supported on $K_{\delta}$. We have the following result:

converges locally uniformly in $\omega\in\Omega$ to a harmonic function on $\Omega$.

We will prove Theorem 15 below. Let us first note that it implies Theorem 4 by proving the following more concrete result.

converges. Now note that (38) is equal to

Now we just need to observe that since $(G_{n})$ is locally convergent, we have that $\frac{|E(G_{n})|}{|V(G_{n})|}=\frac{\text{ind}(K_{2},G)}{2|V(G_{n}|)}$ converges. So (39) implies that the sequence $(n(G_{n})(h))$ is convergent, proving the theorem. ∎

Theorem 16 is stated only for edge-coloring models that are close to the all-ones model. Of course it also applies to edge-coloring models that strictly satisfy the conditions of Corollaries 6a and b. In particular, in view of Remark 1, the result gives a qualitative version of a result of Borgs, Chayes, Kahn and Lovász on ‘right convergence’; see also . We however leave the details to the reader.

We will show that for any graph $G=(V,E)\in\mathcal{G}_{\Delta}$ on $n$ vertices the coefficients of $z^{0},\ldots,z^{m}$ of $q(G)$ can be expressed as a linear combination, over graphs $H$ of at most $(\Delta+1)m$ vertices, of the parameters $\text{ind}(H,G)$. Since $q(G)(z)=k^{-|E(G)|}\sum_{i=0}^{n}a_{n-i}z^{i}$, by (37), this is clearly equivalent to the statement about the coefficients of $\hat{q}$.

So we only need to show that we can express

as a linear combination of the parameters $\text{ind}(H,G)$ for each $i=0,\ldots,m$.

We need the concept of a fragment, which is a pair $(H,\psi)$, where $H$ is a graph and where $\psi$ is a map $\psi:V(H)\to\{0,1,\ldots,\Delta\}$. We think of $\psi(u)$ as a number of half edges sticking out of $u$. For $U\subseteq V$ we let $G(U)$ be the fragment $(G[U],\psi)$ where $\psi(u)$ is equal to the number of edges that connect $u$ with $V\setminus U$. Clearly, for each $U$ of size $i$ the second sum on the right in (40) only depends on the isomorphism class of the fragment $G(U)$. (An isomorphism from a fragment $(H,\psi)$ to a fragment $(H,\psi^{\prime})$ is an isomorphism $\alpha$ of the underlying graphs such that for each $u\in V(H)$, $\psi(u)=\psi^{\prime}(\alpha(u))$.) For a fragment $F=(H,\psi)$ let $E(F)$ denote the set of edges of $F$ including half edges. Then define for an edge-coloring model $y$,

where the sum runs over fragments and where $\text{ind}^{*}(F,G)$ denotes the number of sets $U$ of size $|V(H)|$ such that $G(U)$ is isomorphic to $F=(H,\psi)$.

So to show that (42) can be written as a linear combination of the parameters $\text{ind}(H,G)$ for certain graphs $H$, it suffices to show that we can do this for $\text{ind}^{*}(F,G)$ for any fragment $F$. To see this, note first that we can write

Next, say that $\psi\leq\kappa$ for two maps $\psi,\kappa:V(H)\to\{0,1,\ldots,\Delta\}$ if $\psi(v)\leq\kappa(v)$ for all $v\in V(H)$. This defines a partial order on $[\Delta]^{V(H)}:=\{\psi:V(H)\to\{0,1,\ldots,\Delta\}\}$. Let $Z$ be the associated zeta matrix; that is, $Z$ is the $[\Delta]^{V(H)}\times[\Delta]^{V(H)}$ matrix defined by,

Concluding remarks

In this paper we built on ideas of Barvinok and Soberón to find regions where the partition functions of an edge-coloring models does not evaluate to zero. We moreover used a technique of Barvinok to transform these zero-free regions into quasi-polynomial time approximation algorithms for computing partition functions, as well as for evaluating graph polynomials. This work leads to some questions:

As is indicated by Example 2, our results are not optimal. Can one determine more precisely the region where the partition functions does not evaluate to zero on bounded degree graphs? Recent work of Barvinok indicates that also zero-free regions that are not shaped like a ball are interesting. In he used a strip argument to find a quasi polynomial time algorithm to approximate the permanent of a real matrix $A$ for which $\delta\leq A_{i,j}\leq 1$ for some fixed $\delta>0$.

Can zero-free regions be used in any way to yield (randomized) polynomial time approximation algorithms?

I thank Alexander Barvinok for useful suggestions for the proof of Theorem 6. I am also grateful to Bart Litjens, Sven Polak, Lex Schrijver and Bart Sevenster for their comments. Moreover, I am grateful for useful comments of the anonymous referees.

The research leading to these results has received funding from the European Research Council under the European Union’s Seventh Framework Programme (FP7/2007-2013) / ERC grant agreement n$\mbox{}^{\circ}$ 339109 as well as from a personal NWO VENI grant.

References