scientific article; zbMATH DE number 2151247

MaRDI QIDQ4660717zbMATH OpenFDO

Authors Martin Dyer, Christian Borgs, Jennifer T. Chayes, Prasad Tetali

Publication date 4 April 2005

zbMATH Keywords

conductanceGibbs stategraph homomorphismMarkov chainsmixing timephase coexistencePirogov-Sinai theory

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Randomized algorithms (68W20) Phase transitions (general) in equilibrium statistical mechanics (82B26)

Recommendations

• Counting and sampling \(H\)-colourings
• scientific article; zbMATH DE number 2019624
• Sampling colourings of the triangular lattice
• On systematic scan for sampling H-colorings of the path
• On sampling colorings of bipartite graphs
• Improved bounds for sampling colorings
• Improved bounds for randomly sampling colorings via linear programming
• Improved bounds for perfect sampling of \(k\)-colorings in graphs
• Improved bounds for perfect sampling of k-colorings in graphs
• Perfectly sampling k ≥ (8/3 + o (1))Δ-colorings in graphs

Cited in

(10)

• Algorithmic Pirogov-Sinai theory
• Hit and run as a unifying device
• On Markov chains for randomly H-coloring a graph
• Torpid mixing of local Markov chains on 3-colorings of the discrete torus
• The complexity of approximately counting tree homomorphisms
• Algorithms to approximately count and sample conforming colorings of graphs
• Phase coexistence and torpid mixing in the 3-coloring model on \({\mathbb Z}^d\)
• Slow mixing of Glauber dynamics for the hard-core model on the hypercube
• Homomorphisms from the torus
• H-coloring tori

This page was built for publication:

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