Combinatorial Courant-Fischer-Weyl Minimax Principle on Cheeger k-constants of Weighted Forests

2025/10/07 by Dong Zhang, Meng, Zijun, Zhang, Dong
Mathematics · #Advanced Combinatorial Mathematics #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory #Spectral Theory (math.SP)

paper · pdf · doi:10.48550/arxiv.2510.06301

openalex publication_date 2025/10/07 · openalex created_date 2025/10/18 · openalex updated_date 2026/07/28

Abstract

We establish novel max-min and minimax characterizations of Cheeger k-constants in weighted forests, thereby providing the first combinatorial analogue of the Courant-Fischer-Weyl minimax principle. As for applications, we prove that the forest 1-Laplacian variational eigenvalues are independent of the choice of typical indexes; we propose a refined higher order Cheeger inequality involving numbers of loops of graphs and p-Laplacian eigenvalues; and we present a combinatorial proof for the equality h_k=λ_k(Δ₁) which connects the 1-Laplacian variational eigenvalues and the multiway Cheeger constants.

Citations

• Eigenvalues of the discrete p-Laplacian via graph surgery
• Graph p-Laplacian eigenpairs as saddle points of a family of spectral energy functions
• Gradients of Quotients and Eigenvalue Problems
• The Cheeger Cut and Cheeger Problem in Metric Graphs
• Nodal domain count for the generalized graph p-Laplacian
• Higher order Cheeger inequalities for Steklov eigenvalues
• A nodal domain theorem and a higher-order Cheeger inequality for the\n graph p-Laplacian

Related

• A linear k-fold Cheeger inequality
• Spectral bounds of multi-way Cheeger constants via cyclomatic number
• Cheeger Inequalities for Vertex Expansion and Reweighted Eigenvalues
• Spectrum of the 1-Laplacian and Cheeger's constant on graphs
• Cheeger type inequalities associated with isocapacitary constants on graphs