Eigenvalues and expanders

Research output: Contribution to journalArticlepeer-review

724 Scopus citations

Abstract

Linear expanders have numerous applications to theoretical computer science. Here we show 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 result, which has an analytic analogue for Riemannian manifolds 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. The exact determination of these properties is known to be coNP-complete.

Original languageEnglish (US)
Pages (from-to)83-96
Number of pages14
JournalCombinatorica
Volume6
Issue number2
DOIs
StatePublished - Jun 1986
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Computational Mathematics

Keywords

  • AMS subject classification (1980): 05C99, 05C50, 68E10

Fingerprint

Dive into the research topics of 'Eigenvalues and expanders'. Together they form a unique fingerprint.

Cite this