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

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={\lambda }_k({\Delta }_1)$ which connects the 1-Laplacian variational eigenvalues and the multiway Cheeger constants.

Comments and corrections are very welcome