Paperlane

no. 5 · Friday 30 October 2026

Local-to-Global Theorems Based on Cones with Applications to Graph Coloring

Anqi Li and Shayan Oveis Gharan

math.PR · 26 pp

Abstract

Local-to-Global theorems are a cornerstone of many of recent developments in theoretical computer science from coding theory and PCPs all the way to analyzing mixing time of Markov chains. Building on trickledown theorems on simplicial complexes, several techniques have been established to obtain tighter local-to-global theorems to analyze the spectral gap of the Glauber dynamics, namely matrix trickledown, ${\mathcal C}$-Lorentzian polynomials and more recently Bochner type inequalities. In this paper, we adopt non-local local-to-global/Bochner type inequalities on "cones", corresponding to the local neighborhood of a given vertex, to show that the Glauber dynamics mixes in polynomial time to sample proper colorings of maximum degree $Δ$ graphs as long as $q\geq 1.7408Δ$.

comments
26 pages
fields
Probability, Combinatorics
pdf ↗ page arXiv:2610.37721 ↗