Relative expanders or weakly relatively Ramanujan graphs. (English) Zbl 1035.05058

Let \(G\) be a fixed graph with largest eigenvalue \(\lambda_0\) and with universal cover having spectral radius \(\rho\). The author demonstrates that a random cover of large degree over \(G\) has its new eigenvalues bounded in absolute value by roughly \(\sqrt{\lambda_0\, \rho}\). The main result is a “relative version” of the Broder-Shamir bound on eigenvalues of random regular graphs.


05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C80 Random graphs (graph-theoretic aspects)
68R10 Graph theory (including graph drawing) in computer science
Full Text: DOI


[1] N. Alon, “Eigenvalues and expanders” in Theory of Computing (Singer Island, Fla., 1984) , Combinatorica 6 (1986), 83–96. · Zbl 0661.05053
[2] A. Amit and N. Linial, Random graph coverings, I: General theory and graph connectivity , Combinatorica 22 (2002), 1–18. · Zbl 0996.05105
[3] ——–, Random graph coverings, II : Edge expansion, to appear in Combin. Probab. Comput.
[4] A. Amit, N. Linial, and J. Matoušek, Random lifts of graphs: Independence and chromatic number , Random Structures Algorithms 20 (2002), 1–22. · Zbl 0993.05071
[5] A. Broder and E. Shamir, “On the second eigenvalue of random regular graphs” in 28th Annual Symposium on Foundations of Computer Science (Los Angeles, 1987) , IEEE Comput. Soc. Press, Washington, D.C., 1987, 286–294.
[6] M. W. Buck, Expanders and diffusers , SIAM J. Algebraic Discrete Methods 7 (1986), 282–304. · Zbl 0612.68061
[7] J. Friedman, On the second eigenvalue and random walks in random \(d\)-regular graphs , Combinatorica 11 (1991), 331–362. · Zbl 0760.05078
[8] –. –. –. –., Some geometric aspects of graphs and their eigenfunctions , Duke Math. J. 69 (1993), 487–525. · Zbl 0785.05066
[9] ——–, Relative expansion and an extremal degree two cover of the Boolean cube , preprint, 1994.
[10] ——–, Further remarks on relative expanders , in preparation.
[11] J. Friedman, J. Kahn, and E. Szemerédi, “On the second eigenvalue in random regular graphs” in Proceedings of the 21st Annual ACM Symposium on Theory of Computing (Seattle, 1989) , Association for Computing Machinery, New York, 1989, 587–598.
[12] Y. Greenberg, On the spectrum of graphs and their universal covering (in Hebrew), Ph.D. thesis, Hebrew University, Jerusalem, 1995.
[13] C. Greenhill, S. Janson, J. H. Kim, and N. C. Wormald, Permutation pseudographs and contiguity , Combin. Probab. Comput. 11 (2002), 273–298. \CMP1 909 503 · Zbl 1006.05056
[14] N. Linial and E. Rozenman, Random graph coverings, IV: Perfect matchings , to appear in Combinatorica. · Zbl 1091.05063
[15] A. Lubotzky and T. Nagnibeda, Not every uniform tree covers Ramanujan graphs , J. Combin. Theory Ser. B 74 (1998), 202–212. · Zbl 1024.05021
[16] A. Lubotzky, R. Phillips, and P. Sarnak, Ramanujan graphs , Combinatorica 8 (1988), 261–277. · Zbl 0661.05035
[17] G. A. Margulis, Explicit group-theoretic constructions of combinatorial schemes and their applications in the construction of expanders and concentrators (in Russian), Problemy Peredachi Informatsii 24 , no. 1 (1988), 51–60.
[18] M. Morgenstern, Existence and explicit constructions of \(q+1\) regular Ramanujan graphs for every prime power \(q\) , J. Combin. Theory Ser. B 62 (1994), 44–62. · Zbl 0814.68098
[19] A. Nilli, On the second eigenvalue of a graph , Discrete Math. 91 (1991), 207–210. · Zbl 0771.05064
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.