Eigenvalues and expanders
type: Item
instance of: scholarly article
title: Eigenvalues and expanders
zbMATH Open document ID: 0661.05053
DOI: 10.1007/BF02579166
published in: Combinatorica
publication date: 1986-01-01T00:00:00Z
review text: Let \(G=(V,E)\) be a graph. An \((n,d,c)\)-expander is any bipartite graph on the sets of vertices \(I\) (inputs) and \(O\) (outputs), where \(| I| =| O| =n\), the maximal degree of vertices is \(\underline{d}\), and \[ \operatorname{card} \{v\in V\mid vx\in E\text{ for some }x\in X\}\geq [1+c(1- \alpha /n)]\cdot \alpha, \] whenever \(X\subseteq I\) and \(| X| =\alpha \leq n/2\). In this paper it is shown that a regular bipartite graph is an expander if and only if the second largest eigenvalue of its adjacency matrix is well separated from the first. This enables one to generate expanders randomly and check efficiently their expanding properties. It also supplies an efficient algorithm for approximating the expanding properties of a graph.
reviewed by: Aleksandar Torgašev
Mathematics Subject Classification ID: 05C48
Mathematics Subject Classification ID: 05C50
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 4079476
zbMATH Keywords: eigenvalues of graphs
zbMATH Keywords: regular bipartite graph
zbMATH Keywords: expander
Wikidata QID: Q97007656
author: Noga Alon
MaRDI profile type: Publication
cites work: A note on time-space tradeoffs for computing continuous functions
cites work: Sorting in \(c \log n\) parallel steps
cites work: \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
cites work: Better expanders and superconcentrators
cites work: Asymptotically optimal switching circuits
cites work: Q4770409
cites work: The complexity of testing whether a graph is a superconcentrator
cites work: A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
cites work: On Concentrators, Superconcentrators, Generalizers, and Nonblocking Networks
cites work: Q5682350
cites work: The eigenvalues of random symmetric matrices
cites work: Explicit constructions of linear-sized superconcentrators
cites work: A Topological Application of the Isoperimetric Inequality
cites work: Asymptotically tight bounds on time-space trade-offs in a pebble game
cites work: Q4071451
cites work: The expected eigenvalue distribution of a large regular graph
cites work: Superconcentrators
cites work: Q3947137
cites work: Space bounds for a game on graphs
cites work: Q5514782
cites work: Q3313788
cites work: Explicit Concentrators from Generalized N-Gons
cites work: Time-space tradeoffs for computing functions, using connectivity properties of their circuits
cites work: Graph-theoretic properties in computational complexity
cites work: On the distribution of the roots of certain symmetric matrices
description: scientific article; zbMATH DE number 4079476