arXiv:2610.37721 · v1

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

首次提交 2026-10-27 18:26

版本更新 2026-10-27 18:26

雷达观测 2026-10-30 10:23

摘要

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Δ$.

作者备注：26 pages