Large independent sets via neighborhood block dynamics, Glauber dynamics, and local occupancy
Source: arxiv.org/abs/2611.02483
Local occupancy can be used to bound the expected size of a hard-core independent set. The framework of locally stationary distributions shows that for triangle-free graphs, despite slow mixing at the relevant fugacity parameter, standard Glauber dynamics can be used to find sets close to the local occupancy guarantee. We improve the application of this framework to the hard-core model by replacing a conditional mixing argument with a more direct approach based on a short sequence of single-site updates that, from every initial configuration, achieves the required occupancy inequality. In…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.02483
curl -X POST /api/v1/records/arxiv/2611.02483/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.02483/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'