Explicit bounds from the Alon-Boppana theorem

Abstract: The purpose of this paper is to give explicit methods for bounding the number of vertices of finite

k

-regular graphs with given second eigenvalue. Let

X

be a finite

k

-regular graph and

m u_{1} (X)

the second largest eigenvalue of its adjacency matrix. It follows from the well-known Alon-Boppana Theorem, that for any

e p s i l o n > 0

there are only finitely many such

X

with

m u_{1} (X) < (2 - e p s i l o n) s q r t k - 1

, and we effectively implement Serre's quantitative version of this result. For any

k

and

e p s i l o n

, this gives an explicit upper bound on the number of vertices in a

k

-regular graph with

m u_{1} (X) < (2 - e p s i l o n) s q r t k - 1

.

Recommendations

Cites Work

Cited In (1)

This page was built for publication: Explicit bounds from the Alon-Boppana theorem