Theory of Computing
-------------------
Title : Computing the Partition Function for Cliques in a Graph
Authors : Alexander Barvinok
Volume : 11
Number : 13
Pages : 339-355
URL : http://www.theoryofcomputing.org/articles/v011a013
Abstract
--------
We present a deterministic algorithm which, given a graph $G$ with
$n$ vertices and an integer $1 < m \le n$, computes in $n^{O(\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\{\gamma m
\sigma(S)+O({1}/{m})\}$ provided exactly $\binom{m}{2}\sigma(S)$
pairs of vertices of $S$ span an edge of $G$ for some $0 \leq
\sigma(S) \leq 1$, and $\gamma > 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$.