1. Expander graphs and gaps between primes.
- Author
-
Cioab, Sebastian M., Murty, M. Ram, and Sarnak, Peter
- Subjects
PRIME numbers ,GRAPHIC methods ,MATRICES (Mathematics) ,EIGENVALUES ,MATHEMATICS - Abstract
The explicit construction of infinite families of d-regular graphs which are Ramanujan is known only in the case d – 1 is a prime power. In this paper, we consider the case when d – 1 is not a prime power. The main result is that by perturbing known Ramanujan graphs and using results about gaps between consecutive primes, we are able to construct infinite families of “almost” Ramanujan graphs for almost every value of d. More precisely, for any fixed ℇ > 0 and for almost every value of d (in the sense of natural density), there are infinitely many d-regular graphs such that all the non-trivial eigenvalues of the adjacency matrices of these graphs have absolute value less than (2 + ℇ) . 2000 Mathematics Subject Classification: 05C50, 15A18, 11N05, 11F30. [ABSTRACT FROM AUTHOR]
- Published
- 2008
- Full Text
- View/download PDF