Name
Title | ||
|---|---|---|
Spatial Mixing and Approximation Algorithms for Graphs with Bounded Connective Constant |
Abstract | ||
|---|---|---|
The hard core model in statistical physics is a probability distribution on independent sets in a graph in which the weight of any independent set I is proportional to lambda(|I|), where lambda 0 is the vertex activity. We show that there is an intimate connection between the connective constant of a graph and the phenomenon of strong spatial mixing (decay of correlations) for the hard core model, specifically, we prove that the hard core model with vertex activity lambda; |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1109/FOCS.2013.40 | foundations of computer science |
Keywords | DocType | Volume |
hard core model,strong spatial,spatial mixing,approximation algorithms,vertex activity lambda,vertex activity,independent set,intimate connection,statistical physic,probability distribution,lattice theory,set theory,statistical distributions,approximation theory | Conference | abs/1308.1762 |
ISSN | Citations | PageRank |
0272-5428 | 13 | 0.69 |
References | Authors | |
7 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Alistair Sinclair | 1 | 1506 | 308.40 |
| Piyush Srivastava | 2 | 65 | 4.55 |
| Yitong Yin | 3 | 213 | 23.42 |