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

Research output: Contribution to journalArticle

79 Scopus citations

Abstract

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
JournalCombinatorica
Volume6
Issue number3
DOIs
StatePublished - Sep 1 1986
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Computational Mathematics

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

  • Cite this