## $$\lambda_ 1$$, isoperimetric inequalities for graphs, and superconcentrators.(English)Zbl 0549.05051

A general method for obtaining asymptotic isoperimetric inequalities for families of graphs is developed. Some of these inequalities have been applied to functional analysis. The method uses the second smallest eigenvalue of a certain matrix associated with a graph and it is the discrete version of a method used before for Riemannian manifolds. Some results on Spectra of Graphs showing how this eigenvalue is related to the structure of the graph are also obtained. Combining the new results with some known results on group representations many new explicit examples of linear sized expanders and superconcentrators are constructed.

### MSC:

 05C99 Graph theory 05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
Full Text:

### References:

 [1] Ajtai, M; Komlós, J; Szemerédi, E, Sorting in c log n parallel steps, Combinatorica, 3, 1-19, (1983) · Zbl 0523.68048 [2] Alon, N, Eigenvalues, geometric expanders, sorting in rounds and Ramsey theory, (1984), preprint · Zbl 0625.05026 [3] Alon, N; Milman, V.D, Eigenvalues, expanders and superconcentrators, (), 320-322, Florida · Zbl 0641.68102 [4] Amir, D; Milman, V.D, Unconditional and symmetric sets in n-dimensional normed spaces, Israel J. math., 37, 3-20, (1980) · Zbl 0445.46011 [5] {\scD. Amir and V. D. Milman}, A quantitative finite dimensional Krivine theorem, preprint. · Zbl 0612.46021 [6] Angluin, D, A note on a construction of margulis, Inform. process. lett., 8, 17-19, (1979) · Zbl 0398.94041 [7] Anderson, W.N; Morley, T.D, Eigenvalues of the Laplacian of a graph, (1971), University of Maryland Technical Report TR-71-45 [8] Babai, L, Spectrum of Cayley graphs, J. combin. theory ser. B, 27, 180-189, (1979) · Zbl 0338.05110 [9] Bussemaker, F.C; Čobeljic, S; Cvetković, D.M; Seidel, J.J, Cubic graphs on ≤ 14 vertices, J. combin. theory ser. B, 23, 234-235, (1977) · Zbl 0369.05045 [10] Bussemaker, F.C; Cvetković, D.M; Seidel, J.J, Graphs related to exceptional root systems, (), 185-191 · Zbl 0392.05055 [11] Biggs, N, () [12] Buser, P, On the bipartition of graphs, (), 105-109 · Zbl 0544.05038 [13] Cvetković, D.M; Doob, M; Sachs, H, () [14] Cheeger, J, A lower bound for the smallest eigenvalue of the Laplacian, (), 195-199 · Zbl 0212.44903 [15] Cvetković, D.M, Some possible directions in further investigations of graph spectra, (), 47-67 · Zbl 0471.05043 [16] Donath, W.E; Hoffman, A.J, Lower bounds for the partitioning of graphs, IBM J. res. develop., 17, No. 5, 420-425, (1973) · Zbl 0259.05112 [17] Frankl, P; Füredi, Z, A short proof for a theorem of harper about Hamming spheres, Discrete math., 34, 311-313, (1981) · Zbl 0482.05002 [18] Fiedler, M, Algebraic connectivity of graphs, Czechoslovak. math. J., 23, No. 98, 298-305, (1973) · Zbl 0265.05119 [19] Gabber, O; Galil, Z, Explicit construction of linear sized superconcentrators, J. comput. systems sci., 22, No. 3, 407-420, (1981) · Zbl 0487.05045 [20] Gromov, M, Filling Riemannian manifolds, J. differential geom., 18, 1-147, (1983) · Zbl 0515.53037 [21] Gromov, M; Milman, V.D, A topological application of the isoperimetric inequality, Amer. J. math., 105, 843-854, (1983) · Zbl 0522.53039 [22] Harper, L, Optimal numberings and isoperimetric problems on graphs, J. combin. theory, 1, 385-393, (1966) · Zbl 0158.20802 [23] Kazhdan, D, Connection of the dual space of a group with the structure of its closed subgroups, Funct. anal. appl., 1, 63-65, (1967) · Zbl 0168.27602 [24] Levy, P, Problèmes concrets d’analyse fonctionelle, (1951), Gauthier-Villard Paris [25] Lovász, L, Spectra of graphs with transitive groups, Period. math. hungar., 6, No. 2, 191-195, (1975) · Zbl 0395.05057 [26] Lovász, L, (), Problem 11.8 [27] Margulis, G.A, Explicit construction of concentrators, Problemi peredaci informacii, Problems inform. transmission, 9, No. 4, 325-332, (1975), English transl [28] Maurey, B, Espaces de Banach: construction de suites symétriques, C. R. acad. sci. Paris ser. A-B, 288, A-679-A-681, (1979) · Zbl 0398.46019 [29] {\scV. D. Milman and G. Schechtman}, “Asymptotic Theory of Normed Linear Spaces,” Lecture Notes in Mathematics, to appear. · Zbl 0911.52002 [30] Newman, M, (), 107 [31] Ralston, A, (), Section 10.4 [32] Schechtman, G, Levy type inequality for a class of finite metric spaces, (), 211-215, Lecture Notes in Mathematics [33] Shamir, E, From expanders to better superconcentrators without cascading, (1983), preprint · Zbl 0543.68049 [34] Tanner, R.M, Explicit construction of concentrators from generalized n-gons, SIAM J. algebraic discrete methods, 5, 287-293, (1984) · Zbl 0554.05045 [35] Wang, D.L; Wang, P, Extremal configurations on a discrete torus and a generalization of the generalized macauley theorem, SIAM J. appl. math., 33, 55-59, (1977) · Zbl 0362.05048 [36] Zimmer, R.J, Ergodic theory, group representations, and rigidity, Bull. amer. math. soc. (N.S.), 6, 383-416, (1982) · Zbl 0532.22009
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.