2021/06/07 by Dorna Abdolazimi, Kuikui Liu, Abdolazimi, Dorna +3 · 4 citations
Computer Science · Mathematics · #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Probability (math.PR) #Random Matrices and Applications #Topological and Geometric Data Analysis
paper · pdf · doi:10.48550/arxiv.2106.03845
openalex publication_date 2021/06/07 · openalex created_date 2022/07/25 · openalex updated_date 2026/07/28
We show that the natural Glauber dynamics mixes rapidly and generates a random proper edge-coloring of a graph with maximum degree Δ whenever the number of colors is at least q≥ ((10)/(3) + ε)Δ, where ε>0 is arbitrary and the maximum degree satisfies Δ≥ C for a constant C = C(ε) depending only on ε. For edge-colorings, this improves upon prior work \citeVig99, CDMPP19 which show rapid mixing when q≥ ((11)/(3)-ε0 ) Δ, where ε0 ≈ 10-5 is a small fixed constant. At the heart of our proof, we establish a matrix trickle-down theorem, generalizing Oppenheim's influential result, as a new technique to prove that a high dimensional simplical complex is a local spectral expander.