The Glauber dynamics for edge‐colorings of trees | Zendy

Delcourt Michelle | Zendy; Heinrich Marc | Zendy; Perarnau Guillem | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Premium

The Glauber dynamics for edge‐colorings of trees

Author(s) -

Delcourt Michelle,

Heinrich Marc,

Perarnau Guillem

Publication year - 2020

Publication title -

random structures and algorithms

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 1.314

H-Index - 69

eISSN - 1098-2418

pISSN - 1042-9832

DOI - 10.1002/rsa.20960

Subject(s) - glauber , mathematics , combinatorics , tree (set theory) , monotonic function , ergodic theory , degree (music) , discrete mathematics , enhanced data rates for gsm evolution , upper and lower bounds , block (permutation group theory) , relaxation (psychology) , computer science , pure mathematics , physics , mathematical analysis , scattering , optics , psychology , telecommunications , social psychology , acoustics

Let T be a tree on n vertices and with maximum degree Δ . We show that for k ≥ Δ + 1 the Glauber dynamics for k ‐edge‐ colorings of T mixes in polynomial time in n . The bound on the number of colors is best possible as the chain is not even ergodic for k ≤ Δ . 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.

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research