{"id":"arxiv/2609.35369","url":"https://arxiv.org/abs/2609.35369","tags":["math.CO","cs.DS","math.SP"],"score":0,"title":"A sharp higher-order Cheeger inequality","domain":"math.CO","source":"arxiv","authors":["Yunpeng Li"],"reviews":0,"subject":"math.CO","summary":"Let $λ_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{λ_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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-28","reactions":{}}