We prove a theorem that can be thought of as a common generalization of the Discrete Nodal Theorem and (one direction of) Cheeger’s Inequality for graphs. A special case of this result will assert that if the second and third eigenvalues of the Laplacian are at least ε apart, then the subgraphs induced by the positive and negative supports of the eigenvector belonging to λ2 are not only connected, but edge-expanders (in a weighted sense, with expansion depending on ε).
DOI: https://doi.org/10.37236/9944
L. Lovász: Discrete quantitative nodal theorem, Electr. Journal of Combin. 28 (3) (2021), Research Paper No. 3.58, 6 pp. (online)