A Matrix Trickle-Down Theorem on Simplicial Complexes and Applications to Sampling Colorings


Abstract in English

We show that the natural Glauber dynamics mixes rapidly and generates a random proper edge-coloring of a graph with maximum degree $Delta$ whenever the number of colors is at least $qgeq (frac{10}{3} + epsilon)Delta$, where $epsilon>0$ is arbitrary and the maximum degree satisfies $Delta geq C$ for a constant $C = C(epsilon)$ depending only on $epsilon$. For edge-colorings, this improves upon prior work cite{Vig99, CDMPP19} which show rapid mixing when $qgeq (frac{11}{3}-epsilon_0 ) Delta$, where $epsilon_0 approx 10^{-5}$ is a small fixed constant. At the heart of our proof, we establish a matrix trickle-down theorem, generalizing Oppenheims influential result, as a new technique to prove that a high dimensional simplical complex is a local spectral expander.

Download