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.

MSC:

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

Keywords:

 [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