A strengthening and a multipartite generalization of the Alon-Boppana-Serre theorem

Author:
Bojan Mohar

Journal:
Proc. Amer. Math. Soc. **138** (2010), 3899-3909

MSC (2010):
Primary 05C50

DOI:
https://doi.org/10.1090/S0002-9939-2010-10543-9

Published electronically:
June 22, 2010

MathSciNet review:
2679612

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: The Alon-Boppana theorem confirms that for every $\varepsilon >0$ and every integer $d\ge 3$, there are only finitely many $d$-regular graphs whose second largest eigenvalue is at most $2\sqrt {d-1}-\varepsilon$. Serre gave a strengthening showing that a positive proportion of eigenvalues of any $d$-regular graph must be bigger than $2\sqrt {d-1}-\varepsilon$. We provide a multipartite version of this result. Our proofs are elementary and also work in the case when graphs are not regular. In the simplest, monopartite case, our result extends the Alon-Boppana-Serre result to non-regular graphs of minimum degree $d$ and bounded maximum degree. The two-partite result shows that for every $\varepsilon >0$ and any positive integers $d_1,d_2,d$, every $n$-vertex graph of maximum degree at most $d$, whose vertex set is the union of (not necessarily disjoint) subsets $V_1,V_2$, such that every vertex in $V_i$ has at least $d_i$ neighbors in $V_{3-i}$ for $i=1,2$, has $\Omega _\varepsilon (n)$ eigenvalues that are larger than $\sqrt {d_1-1}+\sqrt {d_2-1}-\varepsilon$. Finally, we strengthen the Alon-Boppana-Serre theorem by showing that the lower bound $2\sqrt {d-1}-\varepsilon$ can be replaced by $2\sqrt {d-1} + \delta$ for some $\delta >0$ if graphs have bounded “global girth”. On the other side of the spectrum, if the odd girth is large, then we get an Alon-Boppana-Serre type theorem for the negative eigenvalues as well.

- N. Alon,
*Eigenvalues and expanders*, Combinatorica**6**(1986), no. 2, 83–96. Theory of computing (Singer Island, Fla., 1984). MR**875835**, DOI https://doi.org/10.1007/BF02579166 - N. Alon and V. D. Milman,
*$\lambda _1,$ isoperimetric inequalities for graphs, and superconcentrators*, J. Combin. Theory Ser. B**38**(1985), no. 1, 73–88. MR**782626**, DOI https://doi.org/10.1016/0095-8956%2885%2990092-9 - P. Cartier,
*Harmonic analysis on trees*, Harmonic analysis on homogeneous spaces (Proc. Sympos. Pure Math., Vol. XXVI, Williams Coll., Williamstown, Mass., 1972) Amer. Math. Soc., Providence, R.I., 1973, pp. 419–424. MR**0338272** - Sebastian M. Cioabă,
*Eigenvalues of graphs and a simple proof of a theorem of Greenberg*, Linear Algebra Appl.**416**(2006), no. 2-3, 776–782. MR**2242462**, DOI https://doi.org/10.1016/j.laa.2005.12.020 - Giuliana Davidoff, Peter Sarnak, and Alain Valette,
*Elementary number theory, group theory, and Ramanujan graphs*, London Mathematical Society Student Texts, vol. 55, Cambridge University Press, Cambridge, 2003. MR**1989434** - E. B. Dynkin and M. B. Maljutov,
*Random walk on groups with a finite number of generators*, Dokl. Akad. Nauk SSSR**137**(1961), 1042–1045 (Russian). MR**0131904** - Keqin Feng and Wen-Ch’ing Winnie Li,
*Spectra of hypergraphs and applications*, J. Number Theory**60**(1996), no. 1, 1–22. MR**1405722**, DOI https://doi.org/10.1006/jnth.1996.0109 - Joel Friedman,
*Some geometric aspects of graphs and their eigenfunctions*, Duke Math. J.**69**(1993), no. 3, 487–525. MR**1208809**, DOI https://doi.org/10.1215/S0012-7094-93-06921-9 - Chris Godsil and Gordon Royle,
*Algebraic graph theory*, Graduate Texts in Mathematics, vol. 207, Springer-Verlag, New York, 2001. MR**1829620** - Y. Greenberg, Spectra of graphs and their covering trees (in Hebrew), Ph.D. thesis, Hebrew University of Jerusalem, 1995.
- Shlomo Hoory,
*A lower bound on the spectral radius of the universal cover of a graph*, J. Combin. Theory Ser. B**93**(2005), no. 1, 33–43. MR**2102266**, DOI https://doi.org/10.1016/j.jctb.2004.06.001 - Shlomo Hoory, Nathan Linial, and Avi Wigderson,
*Expander graphs and their applications*, Bull. Amer. Math. Soc. (N.S.)**43**(2006), no. 4, 439–561. MR**2247919**, DOI https://doi.org/10.1090/S0273-0979-06-01126-8 - Roger A. Horn and Charles R. Johnson,
*Matrix analysis*, Cambridge University Press, Cambridge, 1985. MR**832183** - Harry Kesten,
*Symmetric random walks on groups*, Trans. Amer. Math. Soc.**92**(1959), 336–354. MR**109367**, DOI https://doi.org/10.1090/S0002-9947-1959-0109367-6 - Alexander Lubotzky and Tatiana Nagnibeda,
*Not every uniform tree covers Ramanujan graphs*, J. Combin. Theory Ser. B**74**(1998), no. 2, 202–212. MR**1654133**, DOI https://doi.org/10.1006/jctb.1998.1843 - A. Lubotzky, R. Phillips, and P. Sarnak,
*Ramanujan graphs*, Combinatorica**8**(1988), no. 3, 261–277. MR**963118**, DOI https://doi.org/10.1007/BF02126799 - G. A. Margulis,
*Explicit group-theoretic constructions of combinatorial schemes and their applications in the construction of expanders and concentrators*, Problemy Peredachi Informatsii**24**(1988), no. 1, 51–60 (Russian); English transl., Problems Inform. Transmission**24**(1988), no. 1, 39–46. MR**939574** - Bojan Mohar and Wolfgang Woess,
*A survey on spectra of infinite graphs*, Bull. London Math. Soc.**21**(1989), no. 3, 209–234. MR**986363**, DOI https://doi.org/10.1112/blms/21.3.209 - Moshe Morgenstern,
*Existence and explicit constructions of $q+1$ regular Ramanujan graphs for every prime power $q$*, J. Combin. Theory Ser. B**62**(1994), no. 1, 44–62. MR**1290630**, DOI https://doi.org/10.1006/jctb.1994.1054 - A. Nilli,
*On the second eigenvalue of a graph*, Discrete Math.**91**(1991), no. 2, 207–210. MR**1124768**, DOI https://doi.org/10.1016/0012-365X%2891%2990112-F - A. Nilli,
*Tight estimates for eigenvalues of regular graphs*, Electron. J. Combin.**11**(2004), no. 1, Note 9, 4. MR**2056091** - William L. Paschke,
*Lower bound for the norm of a vertex-transitive graph*, Math. Z.**213**(1993), no. 2, 225–239. MR**1221715**, DOI https://doi.org/10.1007/BF03025720 - Jean-Pierre Serre,
*Répartition asymptotique des valeurs propres de l’opérateur de Hecke $T_p$*, J. Amer. Math. Soc.**10**(1997), no. 1, 75–102 (French). MR**1396897**, DOI https://doi.org/10.1090/S0894-0347-97-00220-8 - Wolfgang Woess,
*Random walks on infinite graphs and groups*, Cambridge Tracts in Mathematics, vol. 138, Cambridge University Press, Cambridge, 2000. MR**1743100**

Retrieve articles in *Proceedings of the American Mathematical Society*
with MSC (2010):
05C50

Retrieve articles in all journals with MSC (2010): 05C50

Additional Information

**Bojan Mohar**

Affiliation:
Department of Mathematics, Simon Fraser University, Burnaby, British Columbia, V5A 1S6, Canada

MR Author ID:
126065

ORCID:
0000-0002-7408-6148

Email:
mohar@sfu.ca

Keywords:
Spectral radius,
eigenvalue,
Ramanujan graph,
universal cover.

Received by editor(s):
February 4, 2010

Published electronically:
June 22, 2010

Additional Notes:
The author was supported in part by the Research Grant P1–0297 of ARRS (Slovenia), by an NSERC Discovery Grant (Canada) and by the Canada Research Chair program.

The author is on leave from IMFM & FMF, Department of Mathematics, University of Ljubljana, Ljubljana, Slovenia.

Communicated by:
Jim Haglund

Article copyright:
© Copyright 2010
American Mathematical Society

The copyright for this article reverts to public domain 28 years after publication.