2015/01/08 by Franklin Kenter, Kenter, Franklin, Mary Radcliffe +1
Chemistry · Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph theory and applications #Probability (math.PR) #Spectral Theory (math.SP) #Synthesis and Properties of Aromatic Compounds #cs.DM #cs.DS #math.CO #math.PR #math.SP
paper · pdf · doi:10.48550/arxiv.1501.01741
8 pages
openalex publication_date 2015/01/08 · arxiv created 2015/02/27 · arxiv updated 2015/03/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given an undirected graph G, the classical Cheeger constant, hG, measures the optimal partition of the vertices into 2 parts with relatively few edges between them based upon the sizes of the parts. The well-known Cheeger's inequality states that 2 λ1 ≤ hG ≤ √ 2 λ1 where λ1 is the minimum nontrivial eigenvalue of the normalized Laplacian matrix. Recent work has generalized the concept of the Cheeger constant when partitioning the vertices of a graph into k > 2 parts. While there are several approaches, recent results have shown these higher-order Cheeger constants to be tightly controlled by λk-1, the (k-1)-th nontrivial eigenvalue, to within a quadratic factor. We present a new higher-order Cheeger inequality with several new perspectives. First, we use an alternative higher-order Cheeger constant which considers an "average case" approach. We show this measure is related to the average of the first k-1 nontrivial eigenvalues of the normalized Laplacian matrix. Further, using recent techniques, our results provide linear inequalities using the ∞-norms of the corresponding eigenvectors. Consequently, unlike previous results, this result is relevant even when λk-1 → 1.