Large independent sets via neighborhood block dynamics, Glauber dynamics, and local occupancy
cs.DS, math.CO
Submitted: 2026-11-02
Updated: 2026-11-02
Comments: 28 pages
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Terminology
Sources
- Sharp bounds for the fractional chromatic number of high-girth $d$-degenerate graphs
- Coloring small locally sparse degenerate graphs and related problems
- On independent sets in random graphs
- On the average size of independent sets in triangle-free graphs
- The hard-core model in graph theory
- An algorithmic framework for colouring locally sparse graphs
- Graph structure via local occupancy
- Fractional coloring via entropy
- Locally Stationary Distributions: A Framework for Analyzing Slow-Mixing Markov Chains
- Local algorithms for independent sets are half-optimal
Related papers
- PHastR: Faster Minimal Perfect Hashing with Rotated Layouts
- Fine-Grained Complexity of Approximating Vector Knapsack: A Faster Algorithm and Equivalence with k-SUM in 2D
- Polynomial-time computation of p-contraction fixed points for even p
- Separations Between Submodular-Like Graph Widths
- Bounded Integer Programming in Almost N 2d Time
- Fast Odd-Permutation Sums in Characteristic Two and Shortest Even Directed Cycles