The Glauber dynamics for edge-colorings of trees

DOI10.1002/RSA.20960MaRDI QIDQ3386527zbMATH OpenOpenAlexFDO

Authors Michelle Delcourt, Marc Heinrich, Guillem Perarnau

Publication date 5 January 2021

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

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

zbMATH Keywords

treesGlauber dynamicsedge-coloringsrapid mixing

Mathematics Subject Classification ID

Trees (05C05) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Coloring of graphs and hypergraphs (05C15)

Abstract: Let $T$ be a tree on $n$ vertices and with maximum degree $Delta$. We show that for $kgeqDelta+1$ the Glauber dynamics for $k$-edge-colourings of $T$ mixes in polynomial time in $n$. The bound on the number of colours is best possible as the chain is not even ergodic for $kleqDelta$. Our proof uses a recursive decomposition of the tree into subtrees; we bound the relaxation time of the original tree in terms of the relaxation time of its subtrees using block dynamics and chain comparison techniques. Of independent interest, we also introduce a monotonicity result for Glauber dynamics that simplifies our proof.

Recommendations

• The Glauber dynamics for colorings of bounded degree trees
• The Glauber Dynamics for Colourings of Bounded Degree Trees
• The mixing time of Glauber dynamics for coloring regular trees
• Very rapid mixing of the Glauber dynamics for proper colorings on bounded‐degree graphs
• The Glauber dynamics of colorings on trees is rapidly mixing throughout the nonreconstruction regime

Cites work

• scientific article; zbMATH DE number 1069282 (Why is no real title available?)
• scientific article; zbMATH DE number 1418384 (Why is no real title available?)
• scientific article; zbMATH DE number 6297817 (Why is no real title available?)
• 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
• Comparison theorems for reversible Markov chains
• Generating uniformly distributed random latin squares
• Gibbs rapidly samples colorings of \(G(n, d/n)\)
• Glauber dynamics on trees and hyperbolic graphs
• Glauber dynamics on trees: Boundary conditions and mixing time
• Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
• Improved bounds for randomly sampling colorings via linear programming
• Improved bounds for sampling colorings
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Randomly coloring sparse random graphs with fewer colors than the maximum degree
• Reconstruction of random colourings
• Sampling random colorings of sparse random graphs
• Systematic scan for sampling colorings
• The Glauber Dynamics for Colourings of Bounded Degree Trees
• The Glauber dynamics for colorings of bounded degree trees
• The Glauber dynamics of colorings on trees is rapidly mixing throughout the nonreconstruction regime
• The mixing time of Glauber dynamics for coloring regular trees
• Uniqueness of uniform random colorings of regular trees

Cited in

(5)

• The Glauber Dynamics on Colorings of a Graph with High Girth and Maximum Degree
• An extension of path coupling and its application to the Glauber dynamics for graph colorings
• The Glauber dynamics for colorings of bounded degree trees
• The Glauber dynamics of colorings on trees is rapidly mixing throughout the nonreconstruction regime
• The Glauber Dynamics for Colourings of Bounded Degree Trees

This page was built for publication: The Glauber dynamics for edge-colorings of trees

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