## 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 language | English (US) |
---|---|

Pages (from-to) | 207-219 |

Number of pages | 13 |

Journal | Combinatorica |

Volume | 6 |

Issue number | 3 |

DOIs | |

State | Published - Sep 1986 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

- Discrete Mathematics and Combinatorics
- Computational Mathematics

## Keywords

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