\(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
type: Item
instance of: scholarly article
title: \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
zbMATH Open document ID: 0549.05051
DOI: 10.1016/0095-8956(85)90092-9
published in: Journal of Combinatorial Theory. Series B
publication date: 1985-01-01T00:00:00Z
review text: A general method for obtaining asymptotic isoperimetric inequalities for families of graphs is developed. Some of these inequalities have been applied to functional analysis. The method uses the second smallest eigenvalue of a certain matrix associated with a graph and it is the discrete version of a method used before for Riemannian manifolds. Some results on Spectra of Graphs showing how this eigenvalue is related to the structure of the graph are also obtained. Combining the new results with some known results on group representations many new explicit examples of linear sized expanders and superconcentrators are constructed.
Mathematics Subject Classification ID: 05C99
Mathematics Subject Classification ID: 05C50
zbMATH DE Number: 3875335
zbMATH Keywords: Laplace operator of a graph
zbMATH Keywords: asymptotic isoperimetric inequalities
zbMATH Keywords: Spectra of Graphs
zbMATH Keywords: linear sized expanders
zbMATH Keywords: superconcentrators
author: Noga Alon
author: Vitali Milman
MaRDI profile type: Publication
full work available at URL: 0095-8956(85)90092-9
OpenAlex ID: W1993111701
Wikidata QID: Q97007892
cites work: Sorting in \(c \log n\) parallel steps
cites work: Eigenvalues, geometric expanders, sorting in rounds, and Ramsey theory
cites work: Better expanders and superconcentrators
cites work: Unconditional and symmetric sets in \(n\)-dimensional normed spaces
cites work: A quantitative finite-dimensional Krivine theorem
cites work: A note on a construction of Margulis
cites work: Spectra of Cayley graphs
cites work: Cubic graphs on \(\leq 14\) vertices
cites work: Q4173399
cites work: Q4770409
cites work: On the bipartition of graphs
cites work: Q3907599
cites work: Q5614192
cites work: Q3924243
cites work: Lower Bounds for the Partitioning of Graphs
cites work: A short proof for a theorem of Harper about Hamming-spheres
cites work: Q5682350
cites work: Explicit constructions of linear-sized superconcentrators
cites work: Filling Riemannian manifolds
cites work: A Topological Application of the Isoperimetric Inequality
cites work: Optimal numberings and isoperimetric problems on graphs
cites work: Connection of the dual space of a group with the structure of its closed subgroups
cites work: Q5806170
cites work: Spectra of graphs with transitive groups
cites work: Q3880849
cites work: Q4183227
cites work: Global versus local asymptotic theories of finite-dimensional normed spaces
cites work: Q5668937
cites work: Q5514782
cites work: Q4751188
cites work: Q3332260
cites work: Explicit Concentrators from Generalized N-Gons
cites work: Extremal Configurations on a Discrete Torus and a Generalization of the Generalized Macaulay Theorem
cites work: Ergodic theory, group representations, and rigidity
Recommended article: \(\lambda_{\infty}\), vertex isoperimetry and concentration
Recommended article: Isoperimetric inequalities for graphs
Recommended article: Isoperimetric inequalities, growth, and the spectrum of graphs
Recommended article: Isoperimetric Inequalities and the Width Parameters of Graphs
Recommended article: Weighted graph Laplacians and isoperimetric inequalities
Recommended article: On the isoperimetric spectrum of graphs and its approximations
Recommended article: The Faber-Krahn type isoperimetric inequalities for a graph
Recommended article: Vertex isoperimetric inequalities for a family of graphs on \(\mathbb{Z}^k\)
Recommended article: Isoperimetric inequalities in graphs and surfaces
Recommended article: Sufficient conditions for graphs to be λ′‐optimal and super‐λ′
description: scientific article; zbMATH DE number 3875335