λ1, Isoperimetric inequalities for graphs, and superconcentrators

Noga Mordechai Alon, V. D. Milman

Research output: Contribution to journalArticle

485 Scopus citations

Abstract

A general method for obtaining asymptotic isoperimetric inequalities for families of graphs is developed. Some of these inequalities have been applied to functional analysis. This method uses the second smallest eigenvalue of a certain matrix associated with the graph and it is the discrete version of a method used before for Riemannian manifolds. Also some results are obtained on spectra of graphs that show how this eigenvalue is related to the structure of the graph. Combining these results with some known results on group representations many new examples are constructed explicitly of linear sized expanders and superconcentrators.

Original languageEnglish (US)
Pages (from-to)73-88
Number of pages16
JournalJournal of Combinatorial Theory, Series B
Volume38
Issue number1
DOIs
StatePublished - Jan 1 1985
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'λ<sub>1</sub>, Isoperimetric inequalities for graphs, and superconcentrators'. Together they form a unique fingerprint.

  • Cite this