Skip to content
DraconiticResearch
Search Sources API
185,139 studies31 sourcesUpdated 34 min ago
PreprintCC BY 4.0arXiv

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

  • Anqi Li
  • Shayan Oveis Gharan
Open at sourcePDFDOICite

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, 𝒞-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≥ 1.7408Δ.

Related

  1. Local-to-Global Isometries in Standard-Norm Generalized Gyrovector Spaces: Thompson and Hilbert Geometries of JB-Cones
    Jyamira Oppekepenguin
    arXivPreprintarXiv licenceFull textAnalysis & PDEsarXiv
  2. Local Tb theorems in non-homogeneous metric spaces, and applications to caloric measure
    Andrea Merlo, Mihalis Mourgoglou, Carmelo Puliatti
    arXivPreprintCC BY 4.0Full textAnalysis & PDEsarXiv
  3. Greedy Coloring and Simple Exponential Strengthenings of Brooks-Type Theorems
    Alex Crane, Carl Feghali, Felicia Lucke +2
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  4. Reinforcement Learning for Global-Local Control of Dynamic Networks with Applications to Systemic Risk
    Nils Detering, Florian Grell, Thilo Meyer-Brandis
    arXivPreprintarXiv licenceFull textOptimisation & controlarXiv
  5. Stabilizer entropy cones as self-dual slices of linear rank cones: a five-party gap and dependence on the local dimension
    Xidan Song, Ruifeng Cao
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsQuantum physics & quantum informationarXiv

Cite

BibTeXRIS
BibTeX
@misc{li2026localtoglobal,
  title = {{Local-to-Global Theorems Based on Cones with Applications to Graph Coloring}},
  author = {Anqi Li and Shayan Oveis Gharan},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.37721},
  eprint = {2610.37721},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.37721},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Local-to-Global Theorems Based on Cones with Applications to Graph Coloring
AU  - Anqi Li
AU  - Shayan Oveis Gharan
PY  - 2026
DA  - 2026/10/27
PB  - arXiv
DO  - 10.48550/arxiv.2610.37721
UR  - https://arxiv.org/abs/2610.37721
AB  - 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, 𝒞-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≥ 1.7408Δ.
ER  -