Skip to content
DraconiticResearch
Search Sources API
203,203 studies31 sourcesUpdated 49 min ago
PreprintarXiv licencearXiv

A sharp higher-order Cheeger inequality

  • Yunpeng Li
Open at sourcePDFDOICite

Abstract

Let λk(G) be the kth eigenvalue of the normalized Laplacian of a finite undirected weighted graph G with positive degrees, where k is an integer satisfying 1≤ k≤ |V(G)|. Let φk(G) be the minimum possible maximum conductance of k disjoint nonempty vertex sets. We prove φk(G)≤ C√(λk(G)log(k+1)) for an absolute constant C. The number of sets and the spectral index are both k, and conductance is measured in the original graph. The logarithmic dependence is optimal up to an absolute constant. The proof combines geometric partitioning of the spectral embedding with minimum-cut improvement and adaptive projections in coefficient space. A single conductance threshold is used throughout the construction. The resulting maps have disjoint supports, and the sum of their Gram matrices is bounded below by an absolute positive multiple of the identity. A dyadic maximal estimate bounds the sum of their internal energies uniformly over unit coefficient vectors. A dimension argument using local eigenvalues then yields exactly k disjoint sparse cuts.

Related

  1. A sharp discrete Sobolev inequality and left inverses of higher order differences
    Raul Hindov, Shahaf Nitzan, Jan-Fredrik Olsen +1
    arXivPreprintCC BY 4.0Full textAnalysis & PDEsarXiv
  2. Higher-order Godbersen inequality and a characterization of simplices via the face lattice
    Filip Fryš, Jan Kotrbatý, Mohamed A. Mouamine +1
    arXivPreprintCC BY 4.0Full textGeometry & topologyarXiv
  3. ADDITIVITY AXIOM FOR THE TORSION FORMS AND HIGHER CHEEGER-MÜLLER/BISMUT-ZHANG THEOREM
    Martin Puchol, Yeping Zhang, Jialin Zhu
    Journal of the Institute of Mathematics of JussieuPeer-reviewedLicence not statedFull text10 citedGeometry & topologyOpenAlex
  4. A Cheeger Inequality for Hypergraphs and Its Applications
    Raj Kamal, Amitabha Bagchi
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  5. Sharp higher-order uncertainty principles
    Hongtao Hu, Meiqi Liu, Wenming Zou
    arXivPreprintCC BY 4.0Full textAnalysis & PDEsarXiv

Cite

BibTeXRIS
BibTeX
@misc{li2026sharp,
  title = {{A sharp higher-order Cheeger inequality}},
  author = {Yunpeng Li},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2609.35369},
  eprint = {2609.35369},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.35369},
}
RIS
TY  - UNPB
TI  - A sharp higher-order Cheeger inequality
AU  - Yunpeng Li
PY  - 2026
DA  - 2026/10/05
PB  - arXiv
DO  - 10.48550/arxiv.2609.35369
UR  - https://arxiv.org/abs/2609.35369
AB  - Let λ_k(G) be the kth eigenvalue of the normalized Laplacian of a finite undirected weighted graph G with positive degrees, where k is an integer satisfying 1≤ k≤ |V(G)|. Let φ_k(G) be the minimum possible maximum conductance of k disjoint nonempty vertex sets. We prove φ_k(G)≤ C√(λ_k(G)log(k+1)) for an absolute constant C. The number of sets and the spectral index are both k, and conductance is measured in the original graph. The logarithmic dependence is optimal up to an absolute constant. The proof combines geometric partitioning of the spectral embedding with minimum-cut improvement and adaptive projections in coefficient space. A single conductance threshold is used throughout the construction. The resulting maps have disjoint supports, and the sum of their Gram matrices is bounded below by an absolute positive multiple of the identity. A dyadic maximal estimate bounds the sum of their internal energies uniformly over unit coefficient vectors. A dimension argument using local eigenvalues then yields exactly k disjoint sparse cuts.
ER  -