Randomly coloring simple hypergraphs

DOI10.1016/j.ipl.2011.06.001zbMath1260.05058OpenAlexW2115314646WikidataQ57401453 ScholiaQ57401453MaRDI QIDQ1944148

Páll Melsted, Alan M. Frieze

Publication date: 4 April 2013

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2011.06.001

zbMATH Keywords

analysis of algorithmsMarkov chainGlauber dynamicsrandom colorings

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Hypergraphs (05C65) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Randomly coloring simple hypergraphs with fewer colors, List coloring triangle-free hypergraphs, Asymptotic enumeration of sparse uniform linear hypergraphs with given degrees, Defective coloring of hypergraphs, Counting Hypergraph Colorings in the Local Lemma Regime

Cites Work

• Unnamed Item
• Unnamed Item
• Absence of phase transition for antiferromagnetic Potts models via the Dobrushin uniqueness theorem
• Improved bounds for sampling colorings
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
• A random polynomial-time algorithm for approximating the volume of convex bodies
• Random walks and anO*(n5) volume algorithm for convex bodies
• A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph