Track new results across pure and applied mathematics.
Search papers, labs, and topics across Lattice.
The paper proves a polylogarithmic higher-order Cheeger inequality, establishing that the $k$-way conductance of any finite weighted undirected graph satisfies $\rho_G(k) \le C [1 + \log(k+1)]^5 \sqrt{\lambda_k(G)}$. The construction yields exactly $k$ disjoint sets in the original graph metric, corresponding to $k$ disjointly supported nonnegative functions with Rayleigh quotients bounded by $O(\log^{10}(k) \lambda_k(G))$. This exponentially improves upon prior polynomial-in-$k$ approximations, settling a long-standing open frontier in spectral graph theory with direct consequences for spectral partitioning.
Multi-way graph partitioning no longer degrades polynomially with the number of clusters, establishing an exponential improvement to an $O(\log^5 k \sqrt{\lambda_k})$ higher-order Cheeger bound.
Let $λ_k(G)$ be the $k$th eigenvalue of the normalized Laplacian of a finite undirected weighted graph, and let $ρ_G(k)$ be the minimum possible maximum conductance of $k$ disjoint nonempty vertex sets. We prove \[ ρ_G(k)\le C[1+\log(k+1)]^5\sqrt{λ_k(G)} \] for an absolute constant $C$. The construction gives exactly $k$ sets and a bound in terms of $λ_k(G)$, with all boundaries and volumes measured in the original graph. More strongly, it yields $k$ nonnegative functions with pairwise disjoint supports and Rayleigh quotients $O([1+\log(k+1)]^{10}λ_k(G))$. The proof uses independent local cutoffs whose lost covariance is controlled by conditioning on the loss along a principal direction in each cell. A regularized spectral embedding bounds cutoff energy on the entire original low eigenspace, while an adaptive construction reduces the remaining coefficient dimension by at least half at each stage. A dimension argument then converts almost rank-one local covariances into exactly $k$ scalar witnesses.