Discrete quantitative nodal theorem

DOI10.37236/9944zbMATH Open1473.05179arXiv1601.06400OpenAlexW3202967365MaRDI QIDQ820852FDOQ820852

Authors: László Lovász 

Publication date: 28 September 2021

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

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).

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

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

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

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)

Cites Work

• Eigenvalues and expanders
• Title not available (Why is that?)
• Perron-Frobenius type results and discrete versions of nodal domain theorems
• Title not available (Why is that?)
• Discrete nodal domain theorems
• Approximating the Permanent
• A short proof of the planarity characterization of Colin de Verdière
• Title not available (Why is that?)
• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
• Title not available (Why is that?)
• Title not available (Why is that?)
• Nodal geometry of graphs on surfaces

Cited In (5)

• Nodal geometry of graphs on surfaces
• Title not available (Why is that?)
• 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)