Eigenvalues, geometric expanders, sorting in rounds, and Ramsey theory. (English) Zbl 0625.05026

Let G be the bipartite graph whose vertices are the points and the hyperplanes of a finite geometry of dimension d and order q, in which a point is adjacent to all the hyperplanes to which it belongs. By estimating the size of the second largest eigenvalue of G, the author shows that G is highly expanding, in the following sense: Any set of x points, \(0<x<n\), is adjacent to at least \(n-(n^{1+1/d}/x)\) hyperplanes. (The number of points is \(n=(q^{d+1}-1)/(q-1).)\) Furthermore, these graphs have, up to a constant, the smallest possible number of edges among graphs with such high expansion property.
Using geometries of dimension 4, the author obtains expanding graphs which are particularly well suited for sorting in rounds, and many bounds for the complexity of explicit algorithms for sorting in rounds are improved, cf. B. Bollobás and the reviewer, Sorting and graphs, Graphs and order, The role of graphs in the theory of ordered sets and its applications, Proc. NATO Adv. Study. Inst., Banff/Can. 1984, NATO ASI Ser., Ser. C 147, 169-184 (1985; Zbl 0579.68041). In particular, the author gives an explicit algorithm for sorting in two rounds with \(O(n^{7/4})\) comparisons. (This was subsequently further improved by Pippenger.)
The author also uses designs and geometries to give other explicit constructions of graphs which were previously proved to exist only by probabilistic arguments. For instance, he shows that the Ramsey number \(r(C_ 4,K_ n)>const\). \(n^{4/3}\).
Reviewer: P.Hell


05C35 Extremal problems in graph theory
05C55 Generalized Ramsey theory
68P10 Searching and sorting
05B25 Combinatorial aspects of finite geometries


Zbl 0579.68041
Full Text: DOI


[1] H. Abelson, A note on time space tradeoffs for computing continuous functions,Infor. Proc. Letters 8 (1979), 215–217. · Zbl 0412.68039
[2] M. Ajtai, J. Komlós andE. Szemerédi, Sorting inc logn parallel steps,Combinatorica 3 (1983), 1–9. · Zbl 0523.68048
[3] N. Alon, Expanders, sorting in rounds and superconcentrators of limited depth,Proc. 17th Annual ACM Symp. on Theory of Computing, Providence, RI (1985), 98–102.
[4] N. Alon, Eigenvalues and expanders,Combinatorica,6 (1986), 83–96. · Zbl 0661.05053
[5] N. Alon, Z. Galil andV. D. Milman, Better expanders and superconcentrators,J. of Algorithms, to appear. · Zbl 0641.68102
[6] 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
[7] N. Alon andV. D. Milman, Eigenvalues, expanders and superconcentrators,Proc. 25 th Annual Symp. on Foundations of Comp. Sci., Florida (1984), 320–322.
[8] B. Bollobás,Extremal Graph Theory, Academic Press, London and New York (1978).
[9] N. G. de Bruijn andP. Erdos, On a combinatorial problem,Indagationes Math. 20 (1948), 421–423.
[10] B. Bollobás andP. Hell, Sorting and Graphs, in:Graphs and Order, (I. Rival, ed.) D. Reidel (1985), 169–184.
[11] B. Bollobás andM. Rosenfeld, Sorting in one round,Israel J. Math. 38 (1981), 154–160. · Zbl 0461.05039
[12] B. Bollobás andA. Thomason, Parallel sorting,Discrete Appl. Math. 6 (1983), 1–11. · Zbl 0507.68035
[13] F. R. K. Chung, On concentrators, superconcentrators, generalizers, and nonblocking networks,Bell Sys. Tech. J. 58 (1978), 1765–1777. · Zbl 0415.94021
[14] P. Erdos, Problems and results in Graph Theory,in: Proc. Inter. 4th Conf. on the theory and applications of graphs (G. Chartrand et al. eds.), Kalamazoo, Michigan (1980), pp. 331–341.
[15] P. Erdos, Extremal problems in Number Theory,Combinatorics and Geometry, Proc. Inter. Conf. in Warsaw, 1983, to appear.
[16] P. Erdos andA. Hajnal, On complete topological subgraphs of certain graphs,Ann. Univ. Sci. Budapest, Eötvös Sect. Math. 7 (1964), 143–149. · Zbl 0125.40501
[17] P. Erdos andA. Rényi, On a problem in the theory of graphs,Publ. Math. Inst. Hungar. Acad. Sci. 7 (1962), 215–235 (in Hungarian).
[18] P. Frankl, V. Rodl andR. M. Wilson, The number of submatrices of given type in a Hadamard martrix,J. of Combinatorial Theory B, to appear.
[19] P. Frankl andR. M. Wilson, Intersection theorems with geometric consequences,Combinatorica 1 (1981), 357–368. · Zbl 0498.05048
[20] O. Gabber andZ. Galil, Explicit construction of linear sized superconcentrators,J. Comp. and Sys. Sci. 22 (1981), 407–420. · Zbl 0487.05045
[21] S. Golomb,Shift Register Sequences, Holden Day, Inc., San Francisco, 1967. · Zbl 0267.94022
[22] R. K. Guy andS. Znam, A problem of Zarankiewicz, in:Recent Progress in Combinatorics (W. T. Tutte, ed.) Academic Press, 1969, 237–243.
[23] M. Hall, Jr.,Combinatorial Theory, Wiley and Sons, New York and London, 1967.
[24] R. Häggkvist andP. Hell, Graphs and parallel comparison algorithms.Congr. Num. 29 (1980), 497–509.
[25] R. Häggkvist andP. Hell, Parallel sorting with constant time for comparisons,SIAM J. Comp. 10, (1981), 465–472. · Zbl 0461.68062
[26] R. Häggkvist andP. Hell, Sorting and merging in rounds,SIAM J. Alg. and Disc. Meth. 3 (1982), 465–473. · Zbl 0493.68060
[27] J. Ja’Ja, Time space tradeoffs for some algebraic problems,Proc. 12 th Ann. ACM Symp. on Theory of Computing, 1980, 339–350.
[28] M. Klawe, Non-existence of one-dimensional expanding graphs,Proc. 22 nd Ann. Symp. Found. Comp. Sci. Nashville (1981). 109–113.
[29] T. Lengauer andR. E. Tarjan, Asymptotically tight bounds on time space trade-offs in a pebble game,J. ACM 29 (1982), 1087–1130. · Zbl 0495.68037
[30] 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
[31] R. Meshuluam, A geometric construction of a superconcentrator of depth 2,preprint.
[32] M. Pinsker, On the complexity of a concentrator,7th International Teletraffic Conference, Stockholm, June 1973, 318/1–318/4.
[33] N. Pippenger, Superconcentrators,SIAM J. Computing 6 (1977), 298–304. · Zbl 0361.05035
[34] N. Pippenger, Advances in pebbling, Internat.Colloq. on Autom. Lang. and Prog. 9 (1982), 407–417. · Zbl 0486.68064
[35] N. Pippenger, Explicit construction of highly expanding graphs,preprint.
[36] W. J. Paul, R. E. Tarjan andJ. R. Celoni, Space bounds for a game on graphs,Math. Sys. Theory 20 (1977), 239–251. · Zbl 0366.90150
[37] S. Scheele,Final report to office of environmental education. Dept. of Health, Education and Welfare, Social Engineering Technology, Los Angeles, CA 1977.
[38] J. Spencer, Asymtotic lower bounds for Ramsey functions,Discrete Math. 20 (1977), 69–76. · Zbl 0375.05033
[39] R. M. Tanner, Explicit construction of concentrators from generalizedN-gons,SIAM J. Alg. Discr. Meth.,5 (1984), 287–293. · Zbl 0554.05045
[40] 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
[41] L. G. Valiant, Paralelism in comparison networks.SIAM J. Comp. 4 (1975), 348–355. · Zbl 0311.68033
[42] L. G. Valiant, Graph theoretic properties in computational complexity,J. Com. and Sys. Sci. 13 (1976), 278–285. · Zbl 0354.68071
[43] N. Alon, Y. Azar, andU. Vizhkin, Tight complexity bounds for parallel comparison sorting,Proc. 27th FOCS, to appear.
[44] A. Lubotzky, R. Phillips, andP. Sarnak, Ramanujan graphs,to appear.
[45] N. Pippenger, Sorting and selecting in rounds,preprint. · Zbl 0654.68068
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.