info:eu-repo/semantics/article
Improved mixing condition on the grid for counting and sampling independent sets
Registro en:
0178-8051
10.1007/s00440-012-0421-8
1432-2064
Autor
Restrepo López, Ricardo
Shin, Jinwoo
Tetali, Prasad
Vigoda, Eric
Yang, Linji
Institución
Resumen
ABSTRACT: The hard-core model has received much attention in the past couple of decades as a lattice gas model with hard constraints in statistical physics, a multicast model of calls in communication networks, and as a weighted independent set problem in combinatorics, probability and theoretical computer science. In this model, each independent set I in a graph G is weighted proportionally to λ|I|, for a positive real
parameter λ. For large λ, computing the partition function (namely, the normalizing constant which makes the weighting a probability distribution on a finite graph) on graphs of maximum degree ≥ 3, is a well known computationally challenging problem. More concretely, let λc(T) denote the critical value for the so-called uniqueness COL0106371