The Glauber dynamics for edge-colorings of trees

DOI10.1002/RSA.20960zbMATH Open1500.05017arXiv1812.05577OpenAlexW3088015146MaRDI QIDQ3386527FDOQ3386527

Authors: Michelle Delcourt, Marc Heinrich, Guillem Perarnau 

Publication date: 5 January 2021

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

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.

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

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

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)

Cites Work

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