Eigenvalues, geometric expanders, sorting in rounds, and ramsey theory

Research output: Contribution to journalArticlepeer-review

86 Scopus citations


Expanding graphs are relevant to theoretical computer science in several ways. Here we show that the points versus hyperplanes incidence graphs of finite geometries form highly (nonlinear) expanding graphs with essentially the smallest possible number of edges. The expansion properties of the graphs are proved using the eigenvalues of their adjacency matrices. These graphs enable us to improve previous results on a parallel sorting problem that arises in structural modeling, by describing an explicit algorithm to sort n elements in k time units using {Mathematical expression} parallel processors, where, e.g., α2=7/4, α3=8/5, α4=26/17 and α5=22/15. Our approach also yields several applications to Ramsey Theory and other extremal problems in combinatorics.

Original languageEnglish (US)
Pages (from-to)207-219
Number of pages13
Issue number3
StatePublished - Sep 1986
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Computational Mathematics


  • AMS subject classification (1980): 68E10, 68E05, 05B25, 05C55


Dive into the research topics of 'Eigenvalues, geometric expanders, sorting in rounds, and ramsey theory'. Together they form a unique fingerprint.

Cite this