Eigenvalues and expanders. (English) Zbl 0661.05053
Let \(G=(V,E)\) be a graph. An \((n,d,c)\)-expander is any bipartite graph on the sets of vertices \(I\) (inputs) and \(O\) (outputs), where \(| I| =| O| =n\), the maximal degree of vertices is \(\underline{d}\), and
\[ \operatorname{card} \{v\in V\mid vx\in E\text{ for some }x\in X\}\geq [1+c(1- \alpha /n)]\cdot \alpha, \]
whenever \(X\subseteq I\) and \(| X| =\alpha \leq n/2\).
In this paper it is shown that a regular bipartite graph is an expander if and only if the second largest eigenvalue of its adjacency matrix is well separated from the first. This enables one to generate expanders randomly and check efficiently their expanding properties. It also supplies an efficient algorithm for approximating the expanding properties of a graph.
\[ \operatorname{card} \{v\in V\mid vx\in E\text{ for some }x\in X\}\geq [1+c(1- \alpha /n)]\cdot \alpha, \]
whenever \(X\subseteq I\) and \(| X| =\alpha \leq n/2\).
In this paper it is shown that a regular bipartite graph is an expander if and only if the second largest eigenvalue of its adjacency matrix is well separated from the first. This enables one to generate expanders randomly and check efficiently their expanding properties. It also supplies an efficient algorithm for approximating the expanding properties of a graph.
Reviewer: Aleksandar Torgašev (Beograd)
MSC:
| 05C48 | Expander graphs |
| 05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |
| 68R10 | Graph theory (including graph drawing) in computer science |
References:
| [1] | H. Abelson, A note on time space tradeoffs for computing continuous functions,Infor. Proc. Letters 8 (1979), 215–217. · Zbl 0412.68039 · doi:10.1016/0020-0190(79)90027-9 |
| [2] | M. Ajtai, J. Komlós andE. Szemerédi, Sorting inc logn parallel steps,Combinatorica 3 (1983), 1–19. · Zbl 0523.68048 · doi:10.1007/BF02579338 |
| [3] | N. Alon andV. D. Milman, {\(\lambda\)}1, isoperimetric inequalities for graphs and superconcentrators,J. Combinatorial Theory Ser. B,38 (1985), 73–88. · Zbl 0549.05051 · doi:10.1016/0095-8956(85)90092-9 |
| [4] | N. Alon andV. D. Milman, Eigenvalues, expanders and superconcentrators,Proc. 25 th Ann. Symp. on Foundations of Comp. Sci., Florida (1984), 320–322. |
| [5] | N. Alon, Z. Galil andV. D. Milman, Better expanders and superconcentrators,to appear. · Zbl 0641.68102 |
| [6] | W. N. Anderson, Jr. andT. D. Morley, Eigenvalues of the Laplacian of a graph,University of Maryland Technical Report TR-71-45, (1971). |
| [7] | L. A. Bassalygo, Asymptotically optimal switching circuits,Problems of Infor. Trans. 17 (1981), 206–211. · Zbl 0486.94021 |
| [8] | N. Biggs,Algebraic Graph Theory, Cambridge University Press, London, 1974. · Zbl 0284.05101 |
| [9] | M. Blum, R. M. Karp, O. Vornberger, C. H. Papadimitriou andM. Yannakakis, The complexity of testing whether a graph is a superconcentrator,Inform. Process. Letters 13 (1981), 164–167. · Zbl 0482.05059 · doi:10.1016/0020-0190(81)90050-8 |
| [10] | B. Bollobás, A. probabilistic proof of an asymptotic formula for the number of labelled regular graphs,Europ. J. Combinatorics 1 (1980), 311–316. · Zbl 0457.05038 |
| [11] | P. Buser, Cubic graphs and the first eigenvalue of a Riemann surface,Math. Z. 162 (1978), 87–99. · doi:10.1007/BF01437826 |
| [12] | J. Cheeger, A lower bound for the smallest eigenvalue of the Laplacian, inProblems in Analysis (edited by R. C. Gunning), Princeton University Press, New Jersey, (1970), 195–199. |
| [13] | F. K. R. Chung, On concentrators, superconcentrators, generalizers and nonblocking networks,Bell Sys. Tech. J. 58 (1978), 1765–1777. · Zbl 0415.94021 |
| [14] | D. M. Cvetkovic, Some possible directions in further investigations of graph spectra, in:Algebraic Methods in Graph Theory (Coll. Math. Soc. J. Bolyai, L. Lovász and V. T. Sós eds.), North-Holland, Amsterdam, (1981) 47–67. |
| [15] | M. Fiedler, Algebraic connectivity of graphs,Czechoslovak. Math. J. 23 (98), (1973), 298–305. · Zbl 0265.05119 |
| [16] | Z. Füredi andJ. Komlós, The eigenvalues of random symmetric matrices,Combinatorica 1 (1981), 233–241. · Zbl 0494.15010 · doi:10.1007/BF02579329 |
| [17] | O. Gabber andZ. Galil, Explicit construction of linear sized superconcentrators,J. Comp. and Sys. Sci. 22 (1981), 407–420. · Zbl 0487.05045 · doi:10.1016/0022-0000(81)90040-4 |
| [18] | M. Gromov andV. D. Milman, A topological application of the isoperimetric inequality,American J. Math. 105 (1983), 843–854. · Zbl 0522.53039 · doi:10.2307/2374298 |
| [19] | J. Ja’Ja, Time space tradeoffs for some algebraic problems,Proc. 12 th Ann. ACM Symp. on Theory of Computing, (1980), 339–350. |
| [20] | S. Jimbo andA. Maruoka, Expanders obtained from affine transformations (extended abstract),preprint (1984). |
| [21] | T. Lengauer andR. E. Tarjan, Asymptotically tight bounds on time space tradeoffs in a pebble game,J. ACM 29 (1982), 1087–1130. · Zbl 0495.68037 · doi:10.1145/322344.322354 |
| [22] | G. A. Margulis, Explicit constructions of concentrators,Prob. Per. Infor. 9 (1973), 71–80. (English translation inProblems of Infor. Trans. (1975), 325–332. · Zbl 0312.22011 |
| [23] | B. D. McKay, The expected eigenvalue distribution of a large regular graph,Linear Algebra Appl. 40 (1981), 203–216. · Zbl 0468.05039 · doi:10.1016/0024-3795(81)90150-6 |
| [24] | M. Pinkser, On the complexity of a concentrator,7 th International Teletraffic Conference, Stockholm, June 1973, 318/1–318/4. |
| [25] | N. Pippenger, Superconcentrators,SIAM J. Computing 6 (1977), 298–304. · Zbl 0361.05035 · doi:10.1137/0206022 |
| [26] | N. Pippenger, Advances in pebbling,Internat. Colloq. on Autom., Langs. and Prog. 9 (1982), 407–417. · Zbl 0486.68064 · doi:10.1007/BFb0012787 |
| [27] | W. J. Paul, R. E. Tarjan andJ. R. Celoni, Space bounds for a game on graphs,Math. Sys. Theory 10 (1977), 239–251. · Zbl 0366.90150 · doi:10.1007/BF01683275 |
| [28] | A. Ralston,A First Course in Numerical Analysis, McGraw-Hill, 1985, Section 10.4. · Zbl 0139.31603 |
| [29] | A. L. Rosenberg, Fault tolerant interconnection networks; a graph theoretic approach, in:Proc. of a Workshop on Graph Theoretic Concepts in Computer Science, Trauner Verlag, Linz (1983), 286–297. · Zbl 0531.94025 |
| [30] | R. M. Tanner, Explicit construction of concentrators from generalizedN-gons,SIAM J. Alg. Discr. Meth. 5 (1984), 287–293. · Zbl 0554.05045 · doi:10.1137/0605030 |
| [31] | M. Tompa, Time space tradeoffs for computing functions using connectivity properties of their circuits,J. Comp. and Sys. Sci. 20 (1980), 118–132. · Zbl 0435.68034 · doi:10.1016/0022-0000(80)90056-2 |
| [32] | L. G. Valiant, Graph theoretic properties in computational complexity,J. Comp. and Sys. Sci. 13 (1976), 278–285. · Zbl 0354.68071 · doi:10.1016/S0022-0000(76)80041-4 |
| [33] | E. P. Wigner, On the distribution of the roots of certain symmetric matrices,Ann. Math. 67 (1958), 325–327. · Zbl 0085.13203 · doi:10.2307/1970008 |
| [34] | A. Lubotzky, R. Phillips, andP. Sarnak, Ramanujan graphs,to appear. |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
