It is shown that if a d-regular graph contains s vertices so that the distance between any pair is at least 4k, then its adjacency matrix has at least s eigenvalues which are at least 2pd − 1 cos( 2k ). A similar result has been proved by Friedman using more sophisticated generally, Serre has shown (see [3], [4] ) that for any fixed r and for any infinite family of d-regular graphs Gi, lim inf r(Gi) 2pd − 1. The same result has been proved by Friedman already in [5]. | Tight estimates for eigenvalues of regular graphs A. Nilli Department of Mathematics Sackler Faculty of Exact Sciences Tel Aviv University Tel Aviv 69978 Israel nilli@ Submitted Apr 4 2004 Accepted May 3 2004 Published May 24 2004 MR Subject Classification 05C50 Abstract It is shown that if a d-regular graph contains s vertices so that the distance between any pair is at least 4k then its adjacency matrix has at least s eigenvalues which are at least 2ựd 1 cos n . A similar result has been proved by Friedman using more sophisticated tools. 1 The main result Let G V E be a simple d-regular graph on n vertices. let A be its adjacency matrix and let A1 G d A2 G . An G be its eigenvalues. Alon and Boppana 1 see also 9 11 proved that for any fixed d and for any infinite family of of d-regular graphs Gi liminf A2 Gi 2 ựd 1. This bound is sharp at least when d 1 is a prime congruent to 1 modulo 4 as shown by the construction of Lubotzky Phillips and Sarnak 9 obtained independently by Margulis 10 . In fact in 1 it is conjectured that almost all d-regular graphs G on n vertices satisfy A2 G 2ỵ d 1 o 1 as n tends to infinity . This has recently been proved by Friedman 6 . More generally Serre has shown see 3 4 that for any fixed r and for any infinite family of d-regular graphs Gi liminf Ar Gi 2 ựd 1. The same result has been proved by Friedman already in 5 . In this note we give an elementary simple proof of this result following the method of 11 . Our estimate is a bit better than that of 11 even for the case r 2 also studied by Kahale in 7 and matches in the first two terms the estimate of Friedman in 5 but the proof is completely elementary. Theorem 1 Let G be a d-regular graph containing s vertices so that the distance between any pair of them is at least 4k. Then As G 2 ựd 1 cos n . THE ELECTRONIC JOURNAL OF COMBINATORICS 11 2004 N9 1 2 The proof Let G V E be a d-regular graph where d 3. Let v E V be a vertex define Vo v and let V be the set of all vertices of
