Improved mixing condition on the grid for counting and sampling independent sets (Q1955841): Difference between revisions
From MaRDI portal
EloiFerrer (talk | contribs) Changed label, description and/or aliases in en, and other parts |
EloiFerrer (talk | contribs) Merged Item from Q5495014 |
||||||||||||||
aliases / en / 0 | aliases / en / 0 | ||||||||||||||
Improved Mixing Condition on the Grid for Counting and Sampling Independent Sets | |||||||||||||||
description / en | description / en | ||||||||||||||
scientific article; zbMATH DE number 6323152 | |||||||||||||||
Property / title | |||||||||||||||
Improved Mixing Condition on the Grid for Counting and Sampling Independent Sets (English) | |||||||||||||||
Property / title: Improved Mixing Condition on the Grid for Counting and Sampling Independent Sets (English) / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / zbMATH Open document ID | |||||||||||||||
Property / zbMATH Open document ID: 1292.60099 / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / DOI | |||||||||||||||
Property / DOI: 10.1109/FOCS.2011.45 / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / published in | |||||||||||||||
Property / published in: 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / publication date | |||||||||||||||
30 July 2014
| |||||||||||||||
Property / publication date: 30 July 2014 / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / Mathematics Subject Classification ID | |||||||||||||||
Property / Mathematics Subject Classification ID: 60K40 / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / Mathematics Subject Classification ID | |||||||||||||||
Property / Mathematics Subject Classification ID: 05C85 / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / Mathematics Subject Classification ID | |||||||||||||||
Property / Mathematics Subject Classification ID: 68W25 / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / Mathematics Subject Classification ID | |||||||||||||||
Property / Mathematics Subject Classification ID: 05C69 / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / zbMATH DE Number | |||||||||||||||
Property / zbMATH DE Number: 6323152 / rank | |||||||||||||||
Normal rank |
Revision as of 09:32, 6 May 2024
scientific article; zbMATH DE number 6323152
- Improved Mixing Condition on the Grid for Counting and Sampling Independent Sets
Language | Label | Description | Also known as |
---|---|---|---|
English | Improved mixing condition on the grid for counting and sampling independent sets |
scientific article; zbMATH DE number 6323152 |
|
Statements
Improved mixing condition on the grid for counting and sampling independent sets (English)
0 references
Improved Mixing Condition on the Grid for Counting and Sampling Independent Sets (English)
0 references
19 June 2013
0 references
30 July 2014
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