Discrete quantitative nodal theorem

DOI10.37236/9944MaRDI QIDQ820852zbMATH OpenOpenAlexFDO

Authors László Lovász

Publication date 28 September 2021

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1601.06400

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

Cheeger's inequality for graphsLaplacian of a connected graph

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Eigenvalues, singular values, and eigenvectors (15A18) Connectivity (05C40)

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. special case of this result will assert that if the second and third eigenvalues of the Laplacian are at least c apart, then the subgraphs induced by the positive and negative supports of the eigenvector belonging to the second eigenvalue are not only connected, but edge-expanders (in a weighted sense, with expansion depending on c).

Recommendations

• Discrete nodal domain theorems
• Courant's Nodal Line Theorem and Its Discrete Counterparts
• scientific article; zbMATH DE number 2042150
• Perron-Frobenius type results and discrete versions of nodal domain theorems
• scientific article; zbMATH DE number 4136988
• Bourgain's discretization theorem
• Discrete Reifenberg-type theorem
• A discrete nodal domain theorem for trees
• Discrete Poincaré lemma
• Discrete Torelli theorem

Cites work

• scientific article; zbMATH DE number 4004190 (Why is no real title available?)
• scientific article; zbMATH DE number 3681933 (Why is no real title available?)
• scientific article; zbMATH DE number 1219775 (Why is no real title available?)
• scientific article; zbMATH DE number 1303522 (Why is no real title available?)
• scientific article; zbMATH DE number 598042 (Why is no real title available?)
• A short proof of the planarity characterization of Colin de Verdière
• Approximating the Permanent
• Discrete nodal domain theorems
• Eigenvalues and expanders
• Nodal geometry of graphs on surfaces
• Perron-Frobenius type results and discrete versions of nodal domain theorems
• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators

Cited in

(5)

• Nodal geometry of graphs on surfaces
• scientific article; zbMATH DE number 878889 (Why is no real title available?)
• Nodal domain theorems for \(p\)-Laplacians on signed graphs
• Discrete nodal domain theorems
• Symmetric matrices, signed graphs, and nodal domain theorems

This page was built for publication: Discrete quantitative nodal theorem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q820852)