Metraipolis › archive › dc_f05709e2ef3f

A sharp higher-order Cheeger inequality — arXiv:2609.35369

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.35369
License (as archived)
CC0-1.0
Archived
2026-10-07T23:29:19.063Z
SHA-256 of the archived text
0a8b89e15ea0c3ae22bc3ad23c78e58b2a3417651ced309ed0a760756c7275de
Stable URL of this page
https://metraipolis.com/documento/dc_f05709e2ef3f

How to cite

A sharp higher-order Cheeger inequality — arXiv:2609.35369 — arXiv (en), https://arxiv.org/abs/2609.35369 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_f05709e2ef3f (Metraipolis archive dc_f05709e2ef3f, sha256 0a8b89e15ea0c3ae22bc3ad23c78e58b2a3417651ced309ed0a760756c7275de)
BibTeX
@misc{dcf05709e2ef3f,
  title = {A sharp higher-order Cheeger inequality — arXiv:2609.35369},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.35369},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_f05709e2ef3f; sha256 0a8b89e15ea0c3ae22bc3ad23c78e58b2a3417651ced309ed0a760756c7275de},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.35369. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Let $\lambda_k(G)$ be the $k$th eigenvalue of the normalized Laplacian of a finite undirected weighted graph $G$ with positive degrees, where $k$ is an integer satisfying $1\le k\le |V(G)|$. Let $\varphi_k(G)$ be the minimum possible maximum conductance of $k$ disjoint nonempty vertex sets. We prove $\varphi_k(G)\le C\sqrt{\lambda_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.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-29 in math.CO).
Categorie arXiv: Combinatorics (math.CO) ; Data Structures and Algorithms (cs.DS); Spectral Theory (math.SP).
Pagina del lavoro: https://arxiv.org/abs/2609.35369 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T23:08:10.862Z dalla pagina https://arxiv.org/catchup/math.CO/2026-09-29?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).