Speaker:
Ricardo Restrepo
Title:
Improved mixing condition for counting and sampling independent sets
Abstract:
We study the hard-core model defined on independent sets of a given
graph $G$. If $I$ is an independent set of $G$, then $I$ receives the
weight $\lambda^{|I|}$ for a positive real parameter lambda. For large
lambda, computing the normalization constant
$Z(\lambda)=\sum\limits_{I \text{ ind. set of } G} \lambda^{|I|}$
(a.k.a., partition function) is a well known computationally
challenging problem. More concretely, in view of breakthrough results
by Dror Weitz (2006) and Allan Sly (2010) for graphs $G$ of maximum
degree $\Delta$ there exists a critical value $\lambda(\Delta)$ such
that the hardness of computing the partition
function undergoes a computational transition.
By improving upon the tree recursion used by Weitz to establish strong
spatial mixing (and therefore polynomial approximability of the
partition function), we develop an improved mixing condition that
allows different `types' among the recursion tree. Such approach
applies to specific classes of graphs. For instance, we prove that
strong spatial mixing holds for subgraphs of the square lattice for
all $\lambda<2.3882$, improving upon the previous bound of $\lambda<1.6875$.
We apply also our criteria to show that the presence of short cycles
everywhere in the graph improves the domain in which strong spatial
mixing holds up to $\lambda<\lambda(\Delta)+\epsilon$, where
$\epsilon$ is a positive constant that depends on the size and density
of such short cycles.
This talk is based on joint work with Jinwoo Shin, Prasad Tetali, Eric
Vigoda and Linji Yang and recent joint work with Prasad Tetali.
PDF of abstract