Improved mixing condition on the grid for counting and sampling independent sets
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 c...
- Autores:
-
Restrepo López, Ricardo
Shin, Jinwoo
Tetali, Prasad
Vigoda, Eric
Yang, Linji
- Tipo de recurso:
- Article of investigation
- Fecha de publicación:
- 2013
- Institución:
- Universidad de Antioquia
- Repositorio:
- Repositorio UdeA
- Idioma:
- eng
- OAI Identifier:
- oai:bibliotecadigital.udea.edu.co:10495/35215
- Acceso en línea:
- https://hdl.handle.net/10495/35215
- Palabra clave:
- Física estadística
Statistical physics
- Rights
- openAccess
- License
- http://creativecommons.org/licenses/by/2.5/co/
| Summary: | 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 |
|---|