Local uniformity properties for Glauber dynamics on graph colorings

DOI10.1002/RSA.20502MaRDI QIDQ2852545zbMATH OpenOpenAlexFDO

Authors Thomas P. Hayes

Publication date 9 October 2013

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/rsa.20502

zbMATH Keywords

graph coloringMarkov chainsmixing times

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Extremal problems in graph theory (05C35) Graph algorithms (graph-theoretic aspects) (05C85) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Randomized algorithms (68W20)

Recommendations

• Sampling random colorings of sparse random graphs
• Very rapid mixing of the Glauber dynamics for proper colorings on bounded‐degree graphs
• scientific article; zbMATH DE number 5279368
• The Glauber Dynamics on Colorings of a Graph with High Girth and Maximum Degree
• Gibbs rapidly samples colorings of \(G(n, d/n)\)

Cites work

• A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph
• Absence of phase transition for antiferromagnetic Potts models via the Dobrushin uniqueness theorem
• Balls and bins: A study in negative dependence
• Coupling with the stationary distribution and improved sampling for colorings and independent sets
• Improved bounds for sampling colorings
• Probability and Computing
• Randomly coloring constant degree graphs
• Randomly coloring graphs with lower bounds on girth and maximum degree
• Randomly Colouring Graphs with Girth Five and Large Maximum Degree
• The Glauber Dynamics on Colorings of a Graph with High Girth and Maximum Degree
• Uniqueness of uniform random colorings of regular trees

Cited in

(3)

• Spectral independence, coupling, and the spectral gap of the Glauber dynamics
• An extension of path coupling and its application to the Glauber dynamics for graph colorings
• Convergence of MCMC and loopy BP in the tree uniqueness region for the hard-core model

This page was built for publication: Local uniformity properties for Glauber dynamics on graph colorings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2852545)