Improved Bounds for Randomly Sampling Colorings via Linear Programming

DOI10.1137/1.9781611975482.134zbMath1432.60089arXiv1810.12980OpenAlexW2898624802MaRDI QIDQ5236321

Michelle Delcourt, Luke Postle, Sitan Chen, Guillem Perarnau, Ankur Moitra

Publication date: 15 October 2019

Published in: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1810.12980

Mathematics Subject Classification ID

Linear programming (90C05) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Coloring of graphs and hypergraphs (05C15)

Related Items (16)

Recoloring Planar Graphs of Girth at Least Five ⋮ On zero-free regions for the anti-ferromagnetic Potts model on bounded-degree graphs ⋮ A polynomial version of Cereceda's conjecture ⋮ List-recoloring of sparse graphs ⋮ An FPTAS for the hardcore model on random regular bipartite graphs ⋮ Perfect sampling from spatial mixing ⋮ Block symmetries in graph coloring reconfiguration systems ⋮ Recoloring graphs of treewidth 2 ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The Glauber dynamics for edge‐colorings of trees ⋮ Weighted counting of solutions to sparse systems of equations ⋮ Counting Hypergraph Colorings in the Local Lemma Regime ⋮ Frozen (Δ + 1)-colourings of bounded degree graphs ⋮ On mixing of Markov chains: coupling, spectral independence, and entropy factorization ⋮ Improved Bounds for Perfect Sampling of $k$-Colorings in Graphs

This page was built for publication: Improved Bounds for Randomly Sampling Colorings via Linear Programming