Discrete Quantitative Nodal Theorem

  • László Lovász

Abstract

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 $\varepsilon$ apart, then the subgraphs induced by the positive and negative supports of the eigenvector belonging to $\lambda_2$ are not only connected, but edge-expanders (in a weighted sense, with expansion depending on $\varepsilon$).

Published
2021-09-24
Article Number
P3.58