Authors Alexander Barvinok,
Journal Theory of Computing
License CC-BY-3.0
T HEORY OF C OMPUTING, Volume 11 (13), 2015, pp. 339–355
www.theoryofcomputing.org
Computing the Partition Function
for Cliques in a Graph
Alexander Barvinok∗
Received June 24, 2014; Revised February 17, 2015; Published December 4, 2015
Abstract: We present a deterministic algorithm which, given a graph G with n vertices
and an integer 1 < m ≤ n, computes in nO(ln m) time the sum of weights w(S) over all m-
subsets S of the set of vertices of G, where w(S) = exp{γmσ (S) + O(1/m)} provided exactly
m
2 σ (S) pairs of vertices of S span an edge of G for some 0 ≤ σ (S) ≤ 1, and γ > 0 is an
absolute constant. This allows us to tell apart the graphs that do not have m-subsets of high
density from the graphs that have sufficiently many m-subsets of high density, even when the
probability to hit such a subset at random is exponentially small in m.
ACM Classification: F.2.1, G.1.2, G.2.2, I.1.2
AMS Classification: 15A15, 68C25, 68W25, 60C05
Key words and phrases: algorithm, clique, partition function, subgraph density, graph
1 Introduction and main results
1.1 Density of a subset in a graph
Let G = (V, E) be an undirected graph with set V of vertices and set E of edges, without loops or multiple
edges. Let S ⊂ V be a subset of the set of vertices of G. We define the density σ (S) of S as the ratio of the
number of the edges of G with both endpoints in S to the maximum possible number of edges spanned by
vertices in S:
|{u, v} ∈ E : u, v ∈ S|
σ (S) = |S|
.
2
∗ Supported by NSF Grants DMS 0856640 and DMS 1361541.
© 2015 Alexander Barvinok
c b Licensed under a Creative Commons Attribution License (CC-BY) DOI: 10.4086/toc.2015.v011a013
A LEXANDER BARVINOK
Hence
0 ≤ σ (S) ≤ 1 for all S ⊂ V.
In particular, σ (S) = 0 if and only if S is an independent set, that is, no two vertices of S span an edge of
G and σ (S) = 1 if and only if S is a clique, that is, every two vertices of S span an edge of G.
In this paper, we suggest a new approach to testing the existence of subsets S of a given size m = |S|
with high density σ (S). Namely, we present a deterministic algorithm, which, given a graph G with n
vertices and an integer 1 < m ≤ n computes in nO(ln m) time (within a relative error of 0.1, say) the sum
Densitym (G) = ∑ exp {γmσ (S) − ε(m)}
S⊂V
|S|=m (1.1)
0.1
where 0 ≤ ε(m) ≤
m−1
and γ > 0 is an absolute constant: we can choose γ = 0.07 and if n ≥ 8m and m ≥ 10 then we can choose
γ = 0.27.
Let us fix two real numbers 0 ≤ σ < σ 0 ≤ 1. If there are no m-subsets S with density σ or higher then
n
Densitym (G) ≤ exp {γmσ − ε(m)} .
m
If, however, there are sufficiently many m-subsets S with density σ 0 or higher, that is, if the probability to
hit such a subset at random is at least 2 exp{−γ(σ 0 − σ )m}, then
n
Densitym (G) ≥ 2 exp {γmσ − ε(m)}
m
and we can distinguish between these two cases in nO(ln m) time. Note that “many subsets" still allows for
the probability to hit such a subset at random to be exponentially small in m.
It turns out that we can compute in nO(ln m) time an m-subset S, which is almost as dense as the average
under the exponential weighting of the formula (1.1), that is, an m-subset S satisfying
1 n −1
exp γmσ (S) ≥ Densitym (G) , (1.2)
2 m
cf. Remark 3.7.
We compute the expression (1.1) using partition functions.
1.2 The partition function of cliques
Let W = (wi j ) be a set of real or complex numbers indexed by unordered pairs {i, j} where 1 ≤ i 6= j ≤ n
and interpreted as a set of weights on the edges of the complete graph with vertices 1, . . . , n. We write wi j
instead of w{i, j} and often refer to W as an n × n symmetric matrix, which should not lead to a confusion
as we never attempt to access the diagonal entries wii .
T HEORY OF C OMPUTING, Volume 11 (13), 2015, pp. 339–355 340
C OMPUTING THE PARTITION F UNCTION FOR C LIQUES IN A G RAPH
For an integer 1 < m ≤ n, we define a polynomial
Pm (W ) = ∑ ∏ wi j ,
S⊂{1,...,n} {i, j}⊂S
|S|=m i6= j
which we call the partition function of cliques (note that it is different from what is known as the partition
function of independent sets, see [20] and [2]). Thus if W is the adjacency matrix of a graph G with set
V = {1, . . . , n} of vertices and set E of edges, so that
(
1 if {i, j} ∈ E,
wi j =
0 otherwise,
then Pm (W ) is the number of cliques in G of size m. Hence computing Pm (W ) is at least as hard as
counting cliques. Let us choose an 0 < α < 1 and modify the weights W as follows:
(
1 if {i, j} ∈ E,
wi j =
α otherwise.
Then Pm (W ) counts all subsets of m vertices in the complete graph on n vertices, only that a subset
spanning exactly k non-edges of G is weighted down by a factor of α k . In other words, an m-subset S ⊂ V
is counted with weight
m
exp 1 − σ (S) ln α .
2
In this paper, we present a deterministic algorithm, which, given an n × n symmetric matrix W = (w j )
such that
γ
wi j − 1 ≤ for all 1 ≤ i 6= j ≤ n (1.3)
m−1
computes the value of Pm (W ) within relative error ε in nO(ln m−ln ε) time. Here γ > 0 is an absolute
constant; we can choose γ = 0.07 and if n ≥ 8m and m ≥ 10, we can choose γ = 0.27.
1.3 The idea of the algorithm
Let J denote the n × n matrix filled with 1s. Given an n × n symmetric matrix W , we consider the
univariate function
f (t) = ln Pm J + t(W − J) . (1.4)
Clearly,
n
f (0) = ln Pm (J) = ln and f (1) = ln Pm (W ) .
m
Hence our goal is to approximate f (1) and we do it by using the Taylor polynomial expansion of f at
t = 0:
`
1 dk
f (1) ≈ f (0) + ∑ k
f (t) . (1.5)
k=1 k! dt t=0
T HEORY OF C OMPUTING, Volume 11 (13), 2015, pp. 339–355 341
A LEXANDER BARVINOK
It turns out that the right hand side of the approximation (1.5) can be computed in nO(`) time. We
present the algorithm in Section 2. The quality of the approximation (1.5) depends on the location of
complex zeros of Pm .
Lemma 1.1. Suppose that there exists a real β > 1 such that
Pm J + z(W − J) 6= 0 for all z ∈ C satisfying |z| ≤ β .
Then the right hand side of the formula (1.5) approximates f (1) within an additive error of
m(m − 1)
.
2(` + 1)β ` (β − 1)
In particular, for a fixed β > 1, to ensure an additive error of 0 < ε < 1, we can choose ` =
O (ln m − ln ε), which results in the algorithm for approximating Pm (W ) within relative error ε in
nO(ln m−ln ε) time. We prove Lemma 1.1 in Section 2.
Thus we have to identify a class of weights W for which the number β > 1 of Lemma 1.1 exists. We
prove the following result.
Theorem 1.2. There is an absolute constant ω > 0 (one can choose ω = 0.071, and if m ≥ 10 and n ≥ 8m,
one can choose ω = 0.271) such that for any positive integers 1 < m ≤ n, for any n × n symmetric complex
matrix Z = (zi j ), we have
Pm (Z) 6= 0
as long as
ω
zi j − 1 ≤ for all 1 ≤ i 6= j ≤ n.
m−1
We prove Theorem 1.2 in Section 3. Theorem 1.2 implies that if the inequality (1.3) holds, where
0 < γ < ω is an absolute constant, we can choose β = ω/γ in Lemma 1.1 and obtain an algorithm which
computes Pm (W ) within a given relative error ε in nO(ln m−ln ε) time. Thus we can choose γ = 0.07 and
β = 71/70 and if m ≥ 10 and n ≥ 8m, we can choose γ = 0.27 and β = 271/270.
1.4 Weighted enumeration of subsets
Given a graph G with set of vertices V = {1, . . . , n} and set E of edges, we define weights W by
(
γ
1 + m−1 if {i, j} ∈ E,
wi j = γ (1.6)
1 − m−1 otherwise,
where γ > 0 is the absolute constant in the inequality (1.3). Thus we can choose γ = 0.07 and if m ≥ 10
and n ≥ 8m, we can choose γ = 0.27. We define the functional (1.1) by
−(m2 )
γm γ
Densitym (G) = e 1+ Pm (W ) .
m−1
T HEORY OF C OMPUTING, Volume 11 (13), 2015, pp. 339–355 342
C OMPUTING THE PARTITION F UNCTION FOR C LIQUES IN A G RAPH
Then we have
Densitym (G) = ∑ w(S) ,
S⊂V
|S|=m
where
(σ (S)−1)(m2 ) (1−σ (S))(m2 )
γm γ γ
w(S) = e 1+ 1−
m−1 m−1
0.1
= exp {γmσ (S) − ε(m)} where 0 ≤ ε(m) ≤
m−1
(in the upper bound for ε(m) we use that γ < 0.3). Thus we are in the situation described in Section 1.1.
1.5 Comparison with results in the literature
The topic of this paper touches upon some very active research areas, such as finding dense subgraphs
in a given graph (see, for example, [7] and references therein), computational complexity of partition
functions (see, for example, [10] and references therein) and complex zeros of partition functions (see,
for example, [20] and references therein). Detecting dense subsets is notoriously hard. It is an NP-hard
problem to approximate the size |S| of the largest clique S within a factor of |V |1−ε for any fixed 0 < ε ≤ 1
[14], [23]. In [11], a polynomial time algorithm for approximating the highest density of an m-subset
within a factor of O(n1/3−ε ) for some small ε > 0 was constructed. The paper [8] presents an algorithm
of nO(1/ε) complexity whichapproximates the highest density of an m-subset within a factor of n1/4+ε
and an algorithm of O nln n complexity which approximates the density within a factor of O(n1/4 ),
the current record (note that [11], [7] and [8] normalize density slightly differently than we do). It has
also been established that modulo some plausible complexity assumptions, it is hard to approximate the
highest density of an m-subset within a constant factor, fixed in advance, see [7].
We note that while searching for a dense m-subset in a graph on n vertices, the most interesting case
to consider is that of a growing m such that m = o(n), since for any fixed ε > 0 one can compute in
polynomial time the maximum number of edges of G spanned by an m-subset S of vertices of G within
an additive error of εn2 [12] (the complexity of the algorithm is exponential in 1/ε). Of course, for any
constant m, fixed in advance, all subsets of size m can be found in polynomial time by an exhaustive
search.
The appearance of partition functions in combinatorics can be traced back to the work of Kaste-
leyn [17] on the statistics of dimers (perfect matchings), see also Section 8.7 of [19]. A randomized
polynomial time approximation algorithm (based on the Markov Chain Monte Carlo approach) for com-
puting the partition function of the classical Ising model was constructed by Jerrum and Sinclair in [16].
A lot of work has recently been done on understanding the computational complexity of the partition
function of graph homomorphisms [10], where a certain “dichotomy” of instances has been established:
it is either #P-hard to compute exactly (in most interesting cases) or it is computable in polynomial
time exactly (in few cases). Recently, an approach inspired by the “correlation decay" phenomenon in
statistical physics was used to construct deterministic approximation algorithms for partition functions in
combinatorial problems [21], [2], [6]. To the best of author’s knowledge, the partition function Pm (W )
introduced in Section 1.2 of this paper has not been studied before and the idea of our algorithm sketched
T HEORY OF C OMPUTING, Volume 11 (13), 2015, pp. 339–355 343
A LEXANDER BARVINOK
in Section 1.3 is also new. On the other hand, one can view our method as inspired by the intuition
from statistical physics. Essentially, the algorithm computes the partition function similar to the one
used in the “simulated annealing" method, see [1], for the temperature that is provably higher than the
phase transition threshold (the role of the “temperature" is played by 1/γm, where γ is the constant in
the density functional (1.1)). The algorithm uses the fact that the partition function has nice analytic
properties at temperatures above the phase transition temperature.
The corollary asserting that graphs without dense m-subsets can be efficiently separated from graphs
with many dense m-subsets is vaguely similar in spirit to the property testing approach [13].
The result requiring most work is Theorem 1.2 bounding the complex roots of the partition function
away from the matrix of all 1s. Studying complex roots of partition functions was initiated by Lee and
Yang [22], [18], continued by Heilmann and Lieb [15], and it is a classical topic by now, because of its
importance to locating the phase transition, see, for example, [20] and Section 8.5 of [19].
The general approach of this paper was first applied by the author [3] to approximate permanents of
matrices that are sufficiently close to the matrix of all 1s (and related expressions, such as hafnians of
symmetric matrices and multidimensional analogues of permanents of tensors). After the first version
of this paper was written, P. Soberón and the author applied this approach to computing the partition
function of graph homomorphisms [5] and its refinement [4]. In each case, the main work consists in
obtaining a version of Theorem 1.2, which bounds the complex roots of the polynomial in question. It is
the easiest in the case of permanents [3] and the most cumbersome in the case of graph homomorphisms
with multiplicities [4]. The most general framework under which the method of this paper works is still
at large.
Open Question 1.3. Is it true that for any γ > 0, fixed in advance, the density functional (1.1) can be
computed (within a relative error of 0.1, say, and some ε(m) = O(1/m)) in nO(ln m) time?
2 The algorithm
2.1 The algorithm for approximating the partition function
Given an n × n symmetric matrix W = (wi j ), we present an algorithm that computes the right hand side
of the approximation (1.5) for the function f (t) defined by formula (1.4).
Let
g(t) = Pm J + t(W − J) = ∑ ∏ 1 + t(wi j − 1) , (2.1)
S⊂{1,...,n} {i, j}⊂S
|S|=m i6= j
so f (t) = ln g(t). Hence
g0 (t)
f 0 (t) = and g0 (t) = g(t) f 0 (t) .
g(t)
Therefore, for k ≥ 1 we have
k−1
dk
j k− j
k−1 d d
g(t) =∑ g(t) f (t) (2.2)
dt k t=0 j=0 j dt j t=0 dt k− j t=0
T HEORY OF C OMPUTING, Volume 11 (13), 2015, pp. 339–355 344
C OMPUTING THE PARTITION F UNCTION FOR C LIQUES IN A G RAPH
(we agree that the 0-th derivative of g is g).
We note that g(0) = mn . If we compute the values of
dk
g(t) for k = 1, . . . , ` , (2.3)
dt k t=0
then the formulas (2.2) for k = 1, . . . , ` provide a non-degenerate triangular system of linear equations
that allows us to compute
dk
f (t) for k = 1, . . . , ` .
dt k t=0
Hence our goal is to compute the values (2.3).
We have
dk
g(t) = ∑ ∑ (wi1 j1 − 1) · · · (wik jk − 1)
dt k t=0
S⊂{1,...,n} I=({i , j },...,{i , j })
1 1 k k
|S|=m {i1 , j1 },...,{ik , jk }⊂S
where the inner sum is taken over all ordered sets I of k distinct pairs {i1 , j1 }, . . ., {ik , jk } of points from
S.
For an ordered set
I = ({i1 , j1 }, . . . , {ik , jk })
of k pairs of points from the set {1, . . . , n}, let
k
[
ρ(I) = {is , js }
s=1
be the total number of distinct points among i1 , j1 , . . . , ik , jk . Since there are exactly
n − ρ(I)
m − ρ(I)
m-subsets S ⊂ {1, . . . , n} containing the pairs {i1 , j1 }, . . ., {ik , jk }, we can further rewrite
dk
n − ρ(I)
g(t) = ∑ (wi1 j1 − 1) · · · (wik jk − 1) ,
dt k t=0
I=({i , j },...,{i , j })
m − ρ(I)
1 1 k k
{i1 , j1 },...,{ik , jk }⊂{1,...,n}
where the sum is taken over all ordered sets I of k distinct pairs {i1 , j1 }, . . . , {ik , jk } of points from the set
{1, . . . , n}. The algorithm consists in computing the latter sum. Since the sum contains not more than
n2k = nO(`) terms, the complexity of the algorithm is indeed nO(`) , as claimed.
2.2 Proof of Lemma 1.1
The function g(z) defined by the equation (2.1) is a polynomial in z of degree d ≤ m2 with g(0) = mn 6= 0,
so we factor
d
z
g(z) = g(0) ∏ 1 − ,
i=1 αi
T HEORY OF C OMPUTING, Volume 11 (13), 2015, pp. 339–355 345
A LEXANDER BARVINOK
where α1 , . . . , αd are the roots of g(z). By the condition of Lemma 1.1, we have
|αi | ≥ β > 1 for i = 1, . . . , d .
Therefore, d
z
f (z) = ln g(z) = ln g(0) + ∑ ln 1 − provided |z| ≤ 1 , (2.4)
i=1 αi
where we choose the branch of ln g(z) that is real at z = 0. Using the standard Taylor expansion, we
obtain
`
1 1 k
1
ln 1 − =−∑ + ζ` ,
αi k=1 k αi
where k
+∞
1 1 1
|ζ` | = ∑ k ≤ .
k=`+1 αi (` + 1)β ` (β − 1)
Therefore, from the equation (2.4) we obtain
` k !
1 d 1
f (1) = f (0) + ∑ − ∑ + η` ,
k=1 k i=1 αi
where
m(m − 1)
|η` | ≤ .
2(` + 1)β ` (β − 1)
It remains to notice that k
1 d 1 1 dk
− ∑ = f (t) .
k i=1 αi k! dt k t=0
3 Proof of Theorem 1.2
3.1 Definitions
For δ > 0, we denote by U(δ ) ⊂ Cn(n−1)/2 the closed polydisc of weights
n o
U(δ ) = Z = (zi j ) : zi j − 1 ≤ δ for all 1 ≤ i 6= j ≤ n .
For a subset Ω ⊂ {1, . . . , n} where 0 ≤ |Ω| ≤ m, we define
PΩ (Z) = ∑ ∏ zi j .
S⊂{1,...,n} {i, j}⊂S
|S|=m i6= j
S⊃Ω
In words: PΩ (Z) is the restriction of the sum defining the clique partition function to the subsets S that
contain a given set Ω. In particular,
P0/ (Z) = Pm (Z) ,
T HEORY OF C OMPUTING, Volume 11 (13), 2015, pp. 339–355 346
C OMPUTING THE PARTITION F UNCTION FOR C LIQUES IN A G RAPH
and if |Ω| < m then
1
PΩ (Z) = PΩ ∪ {i} (Z) . (3.1)
m − |Ω| i: ∑
i∈Ω
/
We note that the natural action of the symmetric group Sn on {1, . . . , n} induces the natural action of Sn
on the space of polynomials in Z which permutes the polynomials PΩ (Z).
First, we establish a simple geometric lemma.
Lemma 3.1. Let u1 , . . . , un ∈ R2 be non-zero vectors such that for some 0 ≤ α < 2π/3 the angle between
any two vectors ui and u j does not exceed α. Let u = u1 + · · · + un . Then
α n
kuk ≥ cos ∑ kui k .
2 i=1
Proof. We observe that the origin does not lie in the convex hull of any three vectors ui , u j , uk since
otherwise the angle between some two of these three vectors is at least 2π/3. The Carathéodory
Theorem then implies that the convex hull of the whole set of vectors u1 , . . . , un does not contain the
origin and hence the vectors lie in an angle at most α with vertex at the origin. The length of the
orthogonal projection of each vector ui onto the bisector of the angle is at least kui k cos(α/2) and hence
the length of the orthogonal projection of u = u1 + · · · + un onto the bisector of the angle is at least
(ku1 k + · · · + kun k) cos(α/2). Since the length of the vector u is at least as large as the length of its
orthogonal projection, the proof follows.
Lemma 3.1 and its proof was suggested by B. Bukh [9]. It replaces an earlier weaker bound used by
the author, see Lemma 3.1 of [3].
We prove Theorem 1.2 by reverse induction on |Ω|, using Lemma 3.1 and the following two lemmas.
Lemma 3.2. Let us fix real 0 < τ < 1, real δ > 0 and an integer 1 ≤ r ≤ m. Suppose that for all
Ω ⊂ {1, . . . , n} such that |Ω| = r, for all Z ∈ U(δ ), we have PΩ (Z) 6= 0 and that for all i = 1, . . . , n we
have
τ ∂
|PΩ (Z)| ≥ zi j PΩ (Z) .
m − 1 j:∑
j6=i ∂ zi j
Then, for any pair of subsets
Ω1 , Ω2 ⊂ {1, . . . , n} such that |Ω1 | = |Ω2 | = r and |Ω1 4 Ω2 | = 2,
and for any Z ∈ U(δ ), the angle between the complex numbers PΩ1 (Z) and PΩ2 (Z), interpreted as vectors
in R2 = C, does not exceed
4δ (m − 1)
θ=
τ(1 − δ )
and the ratio of |PΩ1 (Z)| and |PΩ2 (Z)| does not exceed
4δ (m − 1)
λ = exp .
τ(1 − δ )
T HEORY OF C OMPUTING, Volume 11 (13), 2015, pp. 339–355 347
A LEXANDER BARVINOK
Proof. Let us choose an Ω ∈ {1, . . . , n} such that |Ω| = r. Since PΩ (Z) 6= 0 for all Z ∈ U(δ ), we can
choose a branch of ln PΩ (Z) that is a real number when Z = J. Then
.
∂ ∂
ln PΩ (Z) = PΩ (Z) PΩ (Z) .
∂ zi j ∂ zi j
Since zi j ≥ 1 − δ for all Z ∈ U(δ ), we have
∂ m−1
∑ ∂ zi j ln PΩ (Z) ≤ τ(1 − δ ) for i = 1, . . . , n . (3.2)
j: j6=i
Without loss of generality, we assume that 1 ∈ Ω1 , 2 ∈
/ Ω1 and Ω2 = Ω1 \ {1} ∪ {2}.
Given A ∈ U(δ ), let B ∈ U(δ ) be the weights defined by
b1 j = a2 j and b2 j = a j1 for all j 6= 1, 2
and
bi j = ai j for all other i, j .
Then
PΩ2 (A) = PΩ1 (B)
and
|ln PΩ1 (A) − ln PΩ2 (A)| = |ln PΩ1 (A) − ln PΩ1 (B)|
!
∂ ∂
≤ sup ∑ ln PΩ1 (Z) + ∑ ln PΩ1 (Z)
Z∈U(δ ) j: j6=1,2 ∂ z1 j j: j6=1,2 ∂ z2 j
n o
× max a1 j − b1 j , a2 j − b2 j .
j: j6=1,2
Since ai j − bi j ≤ 2δ for all A, B ∈ U(δ ), by the inequality (3.2) we conclude that the angle between the
complex numbers PΩ1 (A) and PΩ2 (A) does not exceed θ and that the ratio of their absolute values does
not exceed λ .
Lemma 3.3. Let us fix real δ > 0, real 0 ≤ θ < 2π/3, real λ > 1 and an integer 1 < r ≤ m. Suppose
that for all Ω ⊂ {1, . . . , n} such that m ≥ |Ω| ≥ r and for all Z ∈ U(δ ), we have PΩ (Z) 6= 0 and that for
any pair of subsets
Ω1 , Ω2 ⊂ {1, . . . , n} such that m ≥ |Ω1 | = |Ω2 | ≥ r and |Ω1 4 Ω2 | = 2 ,
and for any Z ∈ U(δ ), the angle between two complex numbers PΩ1 (Z) and PΩ2 (Z) considered as vectors
in R2 = C does not exceed θ while the ratio of |PΩ1 (Z)| and |PΩ2 (Z)| does not exceed λ . Let
cos2 (θ /2)
τ= .
λ
T HEORY OF C OMPUTING, Volume 11 (13), 2015, pp. 339–355 348
C OMPUTING THE PARTITION F UNCTION FOR C LIQUES IN A G RAPH
Then, for any subset Ω ⊂ {1, . . . , n} such that |Ω| = r − 1, all Z ∈ U(δ ) and all i = 1, . . . , n, we have
τ ∂
|PΩ (Z)| ≥ ∑ zi j PΩ (Z) . (3.3)
m − 1 j: j6=i ∂ zi j
In addition,
n λ
if ≥ ,
m cos(θ /2)
the inequality (3.3) holds with
τ = cos(θ /2) .
Proof. Let us choose a subset Ω ⊂ {1, . . . , n} such that |Ω| = r − 1. Let us define
Ω j = Ω ∪ { j} for j∈
/ Ω.
Suppose first that i ∈ Ω. Then, for j ∈ Ω \ {i} we have
∂
PΩ (Z) = z−1
i j PΩ (Z)
∂ zi j
and hence
∂
zi j PΩ (Z) = |PΩ (Z)| provided i, j ∈ Ω, i 6= j .
∂ zi j
For j ∈
/ Ω, we have
∂ ∂
PΩ (Z) = PΩ (Z) = z−1
i j PΩ j (Z)
∂ zi j ∂ zi j j
and hence
∂
zi j PΩ (Z) = PΩ j (Z) provided i ∈ Ω and j∈
/ Ω.
∂ zi j
Summarizing,
∂
∑ zi j ∂ zi j PΩ (Z) = (r − 2) |PΩ (Z)| + ∑ PΩ (Z) . j (3.4)
j: j6=i j∈Ω
/
On the other hand, by the equation (3.1), we have
1
PΩ (Z) = PΩ j (Z) .
m − r + 1 j: ∑
j∈Ω
/
By Lemma 3.1, we have
cos(θ /2)
|PΩ (Z)| ≥ PΩ j (Z) (3.5)
m − r + 1 j: ∑
j∈Ω
/
and
θ
(m − 1) |PΩ (Z)| ≥ (r − 2) |PΩ (Z)| + cos PΩ j (Z)
2 j: ∑
j∈Ω
/
T HEORY OF C OMPUTING, Volume 11 (13), 2015, pp. 339–355 349
A LEXANDER BARVINOK
and the inequality (3.3) with τ = cos(θ /2) follows by the formula (3.4).
Suppose now that i ∈ / Ω. Then, for j ∈ Ω, we have
∂ ∂
PΩ (Z) = PΩ (Z) = z−1
i j PΩi (Z)
∂ zi j ∂ zi j i
and hence
∂
zi j PΩ (Z) = |PΩi (Z)| provided i ∈
/Ω and j ∈ Ω. (3.6)
∂ zi j
If r = m then
∂
PΩ (Z) = 0 for any j∈
/Ω
∂ zi j
and
∂
∑ zi j ∂ zi j PΩ (Z) = (m − 1) |PΩ | . i
j: j6=i
By the equation (3.1), we have
PΩ (Z) = ∑ PΩ j (Z)
j∈Ω
/
and hence by Lemma 3.1
θ θ
|PΩ (Z)| ≥ cos PΩ j (Z) ≥ cos |PΩi (Z)| ,
2 j∑∈Ω
/
2
which proves the inequality (3.3) in the case of r = m with τ = cos(θ /2).
If r < m, then for j ∈
/ Ωi , let Ωi j = Ω ∪ {i, j}. Then, for j ∈
/ Ωi , we have
∂ ∂
PΩ (Z) = PΩ (Z) = z−1
i j PΩi j (Z)
∂ zi j ∂ zi j i j
and hence
∂
zi j PΩ (Z) = PΩi j (Z) provided i ∈
/Ω and j∈
/ Ωi .
∂ zi j
From the formula (3.6),
∂
∑ zi j ∂ zi j PΩ (Z) = (r − 1) |PΩ (Z)| + ∑ PΩ (Z)
i ij if r < m. (3.7)
j: j6=i j∈Ω
/ i
By the equation (3.1), we have
1
PΩi (Z) = PΩi j (Z)
m − r j: ∑
j∈Ω
/ i
and hence by Lemma 3.1, we have
cos(θ /2)
|PΩi (Z)| ≥ PΩi j (Z) .
m − r j: ∑
j∈Ω
/ i
T HEORY OF C OMPUTING, Volume 11 (13), 2015, pp. 339–355 350
C OMPUTING THE PARTITION F UNCTION FOR C LIQUES IN A G RAPH
Comparing this with the equation (3.7), we conclude as above that
cos(θ /2) ∂
|PΩi (Z)| ≥ ∑ zi j PΩ (Z) . (3.8)
m − 1 j: j6=i ∂ zi j
It remains to compare |PΩi (Z)| and |PΩ (Z)|. Since the ratio of any two PΩ j1 (Z) , PΩ j2 (Z) does not
exceed λ , from the inequality (3.5) we conclude that
cos(θ /2) n − r + 1
|PΩ (Z)| ≥ |PΩi (Z)| (3.9)
λ m−r+1
cos(θ /2)
≥ |PΩi (Z)| for all i ∈
/ Ω. (3.10)
λ
cos2 (θ /2)
The proof of the inequality (3.3) with τ = follows by the inequality (3.8) and inequality (3.10).
λ
In addition, if
n λ
≥
m cos(θ /2)
then
n−r+1 λ
≥
m−r+1 cos(θ /2)
and the proof of the inequality (3.3) with τ = cos(θ /2) follows by the inequality (3.8) and the inequal-
ity (3.9).
3.2 Proof of Theorem 1.2
One can see that for a sufficiently small ω > 0, the equation
4ω exp{θ }
θ=
(1 − ω) cos2 (θ /2)
has a solution 0 < θ < 2π/3. Numerical computations show that one can choose ω = 0.071, in which
case
θ ≈ 0.6681776075 .
Let
cos2 (θ /2)
λ = exp{θ } ≈ 1.950679176 and τ= ≈ 0.4575206588 .
exp{θ }
Let
ω
δ= .
m−1
For r = m, . . . , 1 we prove the following Statement 3.4, Statement 3.5 and Statement 3.6:
Statement 3.4. Let Ω ⊂ {1, . . . , n} be a set such that |Ω| = r. Then for any Z ∈ U(δ ) we have
PΩ (Z) 6= 0 .
T HEORY OF C OMPUTING, Volume 11 (13), 2015, pp. 339–355 351
A LEXANDER BARVINOK
Statement 3.5. Let Ω ⊂ {1, . . . , n} be a set such that |Ω| = r. Then for any Z ∈ U(δ ), Z = (zi j ), and any
i = 1, . . . , n, we have
τ ∂
|PΩ (Z)| ≥ ∑ zi j PΩ (Z) .
m − 1 j: j6=i ∂ zi j
Statement 3.6. Let Ω1 , Ω2 ⊂ {1, . . . , n} be sets such that |Ω1 | = |Ω2 | = r and |Ω1 4 Ω2 | = 2. Then the
angle between the complex numbers PΩ1 (Z) and PΩ2 (Z), considered as vectors in R2 = C, does not
exceed θ , whereas the ratio of |PΩ1 (Z)| and |PΩ2 (Z)| does not exceed λ .
Suppose that r = m and let Ω ⊂ {1, . . . , n} be a subset such that |Ω| = m. Then
PΩ (Z) = ∏ zi j ,
{i, j}⊂Ω
i6= j
so Statement 3.4 clearly holds for r = m. Moreover, for i ∈ Ω, we have
∂
∑ zi j ∂ zi j PΩ (Z) = (m − 1) |PΩ (Z)| ,
j: j6=i
while for i ∈
/ Ω, we have
∂
∑ zi j ∂ zi j PΩ (Z) = 0 ,
j: j6=i
so Statement 3.5 holds for r = m as well.
Lemma 3.2 implies that if Statement 3.4 and Statement 3.5 hold for sets Ω of cardinality r then for
any two subsets Ω1 , Ω2 ⊂ {1, . . . , n} such that |Ω1 | = |Ω2 | = r and |Ω1 4 Ω2 | = 2 the angle between the
two (necessarily non-zero) complex numbers PΩ1 (Z) and PΩ2 (Z) does not exceed
4δ (m − 1) 4ω 4ω exp{θ } 4ω exp{θ }
= = ≤ =θ
τ(1 − δ ) ω
1 − m−1 τ ω 2
1 − m−1 cos (θ /2) (1 − ω) cos2 (θ /2)
while the ratio of |PΩ1 (Z)| and |PΩ2 (Z)| does not exceed
( )
4δ (m − 1) 4ω exp{θ } 4ω exp{θ }
exp = exp ≤ exp
τ(1 − δ ) ω
1 − m−1 cos2 (θ /2) (1 − ω) cos2 (θ /2)
= exp{θ } = λ
and hence Statement 3.6 holds for sets Ω of cardinality r.
Lemma 3.3 implies that if Statement 3.4 and Statement 3.6 hold for sets Ω of cardinality r then
Statement 3.5 holds for sets Ω of cardinality r − 1. Formula (3.1), Lemma 3.1, Statement 3.4 and
Statement 3.6 for sets Ω of cardinality r imply Statement 3.4 for sets Ω of cardinality r − 1. Therefore,
we conclude that Statement 3.4 and Statement 3.6 hold for sets Ω such that |Ω| = 1. Formula (3.1) and
Lemma 3.1 imply then that
P0/ (Z) = Pm (Z) 6= 0 ,
T HEORY OF C OMPUTING, Volume 11 (13), 2015, pp. 339–355 352
C OMPUTING THE PARTITION F UNCTION FOR C LIQUES IN A G RAPH
as desired.
A more careful analysis establishes that if m ≥ 10 then for ω = 0.271 the equation
4ω
θ= ω
1 − m−1 cos(θ /2)
has a solution
0 < θ < 1.626699443
with
λ
λ = exp{θ } < 5.1 and cos(θ /2) > 0.68 so that < 7.5 .
cos(θ /2)
Then, if n ≥ 8m, we let
ω
δ= , τ = cos(θ /2)
m−1
and the proof proceeds as above.
Remark 3.7. As follows from Statement 3.4, we have PΩ (Z) 6= 0 for any complex weights Z = (zi j )
satisfying the conditions of Theorem 1.2. The algorithm of Section 2 extends in a straightforward way
to computing PΩ (W ) for every weights W = (wi j ) satisfying the inequality (1.3). This allows us to
compute in nO(ln m) time by successive conditioning an m-subset S which satisfies the inequality (1.2).
Namely, we define weights W by the formula (1.6) and construct subsets S0 , . . . , Sm ⊂ {1, . . . , n}, where
S0 = 0/ and |Si | = i as follows. Assuming that Si−1 is constructed, for each j ∈ {1, . . . , n} \ Si−1 , we let
Ω j = Si−1 ∪ { j} and compute PΩ j (W ) within a relative error of 1/10m. We then select j with the largest
computed value of PΩ j (W ) and let Si = Ω j . The set S = Sm satisfies the inequality (1.2).
Acknowledgments
I am grateful to Alex Samorodnitsky and Benny Sudakov for several useful remarks, to anonymous
referees for their comments and critique, in particular, for pointing out to [7] and to Boris Bukh for
suggesting Lemma 3.1.
References
[1] ROBERT A ZENCOTT: Simulated annealing. Astérisque, 1987/88(161-162):223–237, 1988. Sémi-
naire Bourbaki 30 No. 697. Available at Numdam. 344
[2] A NTAR BANDYOPADHYAY AND DAVID G AMARNIK: Counting without sampling: A symptotics of
the log-partition function for certain statistical physics models. Random Structures & Algorithms,
33(4):452–479, 2008. [doi:10.1002/rsa.20236] 341, 343
[3] A LEXANDER BARVINOK: Computing the permanent of (some) complex matrices. Foundations of
Computational Mathematics, pp. 1–14, 2015. [doi:10.1007/s10208-014-9243-7, arXiv:1405.1303]
344, 347
T HEORY OF C OMPUTING, Volume 11 (13), 2015, pp. 339–355 353
A LEXANDER BARVINOK
[4] A LEXANDER BARVINOK AND PABLO S OBERÓN: Computing the partition function for
graph homomorphisms with multiplicities. J. Combinat. Theory, Ser. A, 137:1–26, 2016.
[doi:10.1016/j.jcta.2015.08.001, arXiv:1410.1842] 344
[5] A LEXANDER BARVINOK AND PABLO S OBERÓN: Computing the partition function for graph
homomorphisms. Combinatorica, to appear. [arXiv:1406.1771] 344
[6] M OHSEN BAYATI , DAVID G AMARNIK , D IMITRIY K ATZ , C HANDRA NAIR , AND P RASAD T ETALI:
Simple deterministic approximation algorithms for counting matchings. In Proc. 39th STOC, pp.
122–127, New York, 2007. ACM Press. [doi:10.1145/1250790.1250809] 343
[7] A DITYA B HASKARA: Finding Dense Structures in Graphs and Matrices. Ph. D. thesis, Princeton
University, 2012. Available at author’s website. 343, 353
[8] A DITYA B HASKARA , M OSES C HARIKAR , E DEN C HLAMTÁC , U RIEL F EIGE , AND A RAVINDAN
V IJAYARAGHAVAN: Detecting high log-densities – an O(n1/4 ) approximation for densest k-subgraph.
In Proc. 42nd STOC, pp. 201–210, New York, 2010. ACM Press. [doi:10.1145/1806689.1806719,
arXiv:1001.2891] 343
[9] B ORIS B UKH: Personal communication, 2015. 347
[10] A NDREI A. B ULATOV AND M ARTIN G ROHE: The complexity of partition functions.
Theoret. Comput. Sci., 348(2-3):148–186, 2005. Preliminary version in ICALP’04.
[doi:10.1016/j.tcs.2005.09.011] 343
[11] U RIEL F EIGE , G UY KORTSARZ , AND DAVID P ELEG: The dense k-subgraph problem. Algorith-
mica, 29(3):410–421, 2001. [doi:10.1007/s004530010050] 343
[12] A LAN F RIEZE AND R AVI K ANNAN: Quick approximation to matrices and applications. Combina-
torica, 19(2):175–220, 1999. [doi:10.1007/s004930050052] 343
[13] O DED G OLDREICH , S HAFI G OLDWASSER , AND DANA RON: Property testing and its connection
to learning and approximation. J. ACM, 45(4):653–750, 1998. Preliminary versions in FOCS’96
and ECCC. [doi:10.1145/285055.285060] 344
[14] J OHAN H ÅSTAD: Clique is hard to approximate within n1−ε . Acta Mathematica, 182(1):105–142,
1999. Preliminary version in FOCS’96. [doi:10.1007/BF02392825] 343
[15] O LE J. H EILMANN AND E LLIOTT H. L IEB: Theory of monomer-dimer systems. Comm. Math.
Phys., 25(3):190–232, 1972. Available at project euclid. [doi:10.1007/BF01877590] 344
[16] M ARK J ERRUM AND A LISTAIR S INCLAIR: Polynomial-time approximation algorithms for the
Ising model. SIAM J. Comput., 22(5):1087–1116, 1993. Preliminary version in ICALP’90.
[doi:10.1137/0222066] 343
[17] P IETER W ILLEM K ASTELEYN: Dimer statistics and phase transitions. J. Math. Phys., 4(2):287–293,
1963. [doi:10.1063/1.1703953] 343
T HEORY OF C OMPUTING, Volume 11 (13), 2015, pp. 339–355 354
C OMPUTING THE PARTITION F UNCTION FOR C LIQUES IN A G RAPH
[18] T SUNG -DAO L EE AND C HEN -N ING YANG: Statistical theory of equations of state and
phase transitions. II. Lattice gas and Ising model. Phys. Rev., 87(3):410–419, 1952.
[doi:10.1103/PhysRev.87.410] 344
[19] L ÁSZLÓ L OVÁSZ AND M ICHAEL D. P LUMMER: Matching Theory. AMS Chelsea Publishing,
Providence, RI, corrected reprint of the 1986 original edition, 2009. 343, 344
[20] A LEXANDER D. S COTT AND A LAN D. S OKAL: The repulsive lattice gas, the independent-set poly-
nomial, and the Lovász local lemma. J. Stat. Phys., 118(5-6):1151–1261, 2005. [doi:10.1007/s10955-
004-2055-4, arXiv:cond-mat/0309352] 341, 343, 344
[21] D ROR W EITZ: Counting independent sets up to the tree threshold. In Proc. 38th STOC, pp. 140–149,
New York, 2006. ACM Press. [doi:10.1145/1132516.1132538] 343
[22] C HEN -N ING YANG AND T SUNG -DAO L EE: Statistical theory of equations of state and phase tran-
sitions. I. Theory of condensation. Phys. Rev., 87(3):404–409, 1952. [doi:10.1103/PhysRev.87.404]
344
[23] DAVID Z UCKERMAN: Linear degree extractors and the inapproximability of max clique and
chromatic number. Theory of Computing, 3(6):103–128, 2007. Preliminary version in STOC’06.
[doi:10.4086/toc.2007.v003a006] 343
AUTHOR
Alexander Barvinok
Professor of Mathematics
University of Michigan, Ann Arbor, MI
barvinok umich edu
http://www.math.lsa.umich.edu/~barvinok
ABOUT THE AUTHOR
A LEXANDER BARVINOK graduated from the Leningrad (now St. Petersburg) State Univer-
sity in USSR (now Russia) in 1988; his advisor was Anatoly Vershik. His thesis was on
the combinatorics and computational complexity of polytopes with symmetry. He is still
interested in polytopes, symmetry and complexity. For the past 20+ years he has been
living in Ann Arbor and he kind of likes it there.
T HEORY OF C OMPUTING, Volume 11 (13), 2015, pp. 339–355 355