Improved mixing condition on the grid for counting and sampling independent sets (Q1955841): Difference between revisions
From MaRDI portal
Changed an Item |
EloiFerrer (talk | contribs) Changed label, description and/or aliases in en, and other parts |
||
description / en | description / en | ||
Revision as of 15:05, 2 May 2024
No description defined
Language | Label | Description | Also known as |
---|---|---|---|
English | Improved mixing condition on the grid for counting and sampling independent sets |
No description defined |
Statements
Improved mixing condition on the grid for counting and sampling independent sets (English)
0 references
19 June 2013
0 references
The authors study phase transitions for sampling weighted (by an activity \(\lambda\)) independent sets of the two-dimensional integer lattice, and their paper is based upon the work by Weitz who derived some results on the counting of independent sets up to the tree threshold. This problem has many practical applications and is involved, for instance, in the computational complexity of the partition function in physics. The background is based on weak and strong spatial mixing, and on self-avoiding walk tree representation. Strong spatial mixing (SSM) and weak spatial mixing (WSM) are defined, which can be understood by the following intuition. If a pair of boundary configurations on a subset \(S\) agrees at some vertices in \(S\), then those vertices encourage \(v\) to agree. The contribution of the paper is a criterion which achieves better bounds (than those of Weitz) on SSM for trees when the trees have extra structure. The relation with the Ising model is outlined in the conclusion.
0 references
lattice gas
0 references
Gibbs measures
0 references
phase transition
0 references
approximation algorithm
0 references
Glauber dynamics
0 references