{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T08:54:28Z","timestamp":1773219268732,"version":"3.50.1"},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[1986,9,1]],"date-time":"1986-09-01T00:00:00Z","timestamp":525916800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[1986,9]]},"DOI":"10.1007\/bf02579382","type":"journal-article","created":{"date-parts":[[2007,3,22]],"date-time":"2007-03-22T22:20:17Z","timestamp":1174602017000},"page":"207-219","source":"Crossref","is-referenced-by-count":76,"title":["Eigenvalues, geometric expanders, sorting in rounds, and ramsey theory"],"prefix":"10.1007","volume":"6","author":[{"given":"Noga","family":"Alon","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"BF02579382_CR1","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1016\/0020-0190(79)90027-9","volume":"8","author":"H. Abelson","year":"1979","unstructured":"H. Abelson, A note on time space tradeoffs for computing continuous functions,Infor. Proc. Letters 8 (1979), 215\u2013217.","journal-title":"Infor. Proc. Letters"},{"key":"BF02579382_CR2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF02579338","volume":"3","author":"M. Ajtai","year":"1983","unstructured":"M. Ajtai, J. Koml\u00f3s andE. Szemer\u00e9di, Sorting inc logn parallel steps,Combinatorica 3 (1983), 1\u20139.","journal-title":"Combinatorica"},{"key":"BF02579382_CR3","doi-asserted-by":"crossref","unstructured":"N. Alon, Expanders, sorting in rounds and superconcentrators of limited depth,Proc. 17th Annual ACM Symp. on Theory of Computing, Providence, RI (1985), 98\u2013102.","DOI":"10.1145\/22145.22156"},{"key":"BF02579382_CR4","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1007\/BF02579166","volume":"6","author":"N. Alon","year":"1986","unstructured":"N. Alon, Eigenvalues and expanders,Combinatorica,6 (1986), 83\u201396.","journal-title":"Combinatorica"},{"key":"BF02579382_CR5","unstructured":"N. Alon, Z. Galil andV. D. Milman, Better expanders and superconcentrators,J. of Algorithms, to appear."},{"key":"BF02579382_CR6","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1016\/0095-8956(85)90092-9","volume":"38","author":"N. Alon","year":"1985","unstructured":"N. Alon andV. D. Milman, \u03bb1, isoperimetric inequalities for graphs and superconcentrators,J. Combinatorial Theory Ser. B,38 (1985), 73\u201388.","journal-title":"J. Combinatorial Theory Ser. B"},{"key":"BF02579382_CR7","doi-asserted-by":"crossref","unstructured":"N. Alon andV. D. Milman, Eigenvalues, expanders and superconcentrators,Proc. 25 th Annual Symp. on Foundations of Comp. Sci., Florida (1984), 320\u2013322.","DOI":"10.1109\/SFCS.1984.715931"},{"key":"BF02579382_CR8","volume-title":"Extremal Graph Theory","author":"B. Bollob\u00e1s","year":"1978","unstructured":"B. Bollob\u00e1s,Extremal Graph Theory, Academic Press, London and New York (1978)."},{"key":"BF02579382_CR9","first-page":"421","volume":"20","author":"N. G. Bruijn de","year":"1948","unstructured":"N. G. de Bruijn andP. Erd\u0151s, On a combinatorial problem,Indagationes Math. 20 (1948), 421\u2013423.","journal-title":"Indagationes Math."},{"key":"BF02579382_CR10","doi-asserted-by":"crossref","unstructured":"B. Bollob\u00e1s andP. Hell, Sorting and Graphs, in:Graphs and Order, (I. Rival, ed.) D. Reidel (1985), 169\u2013184.","DOI":"10.1007\/978-94-009-5315-4_5"},{"key":"BF02579382_CR11","doi-asserted-by":"crossref","first-page":"154","DOI":"10.1007\/BF02761857","volume":"38","author":"B. Bollob\u00e1s","year":"1981","unstructured":"B. Bollob\u00e1s andM. Rosenfeld, Sorting in one round,Israel J. Math. 38 (1981), 154\u2013160.","journal-title":"Israel J. Math."},{"key":"BF02579382_CR12","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0166-218X(83)90095-1","volume":"6","author":"B. Bollob\u00e1s","year":"1983","unstructured":"B. Bollob\u00e1s andA. Thomason, Parallel sorting,Discrete Appl. Math. 6 (1983), 1\u201311.","journal-title":"Discrete Appl. Math."},{"key":"BF02579382_CR13","doi-asserted-by":"crossref","first-page":"1765","DOI":"10.1002\/j.1538-7305.1979.tb02972.x","volume":"58","author":"F. R. K. Chung","year":"1978","unstructured":"F. R. K. Chung, On concentrators, superconcentrators, generalizers, and nonblocking networks,Bell Sys. Tech. J. 58 (1978), 1765\u20131777.","journal-title":"Bell Sys. Tech. J."},{"key":"BF02579382_CR14","unstructured":"P. Erd\u0151s, 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\u2013341."},{"key":"BF02579382_CR15","unstructured":"P. Erd\u0151s, Extremal problems in Number Theory,Combinatorics and Geometry, Proc. Inter. Conf. in Warsaw, 1983, to appear."},{"key":"BF02579382_CR16","first-page":"143","volume":"7","author":"P. Erd\u0151s","year":"1964","unstructured":"P. Erd\u0151s andA. Hajnal, On complete topological subgraphs of certain graphs,Ann. Univ. Sci. Budapest, E\u00f6tv\u00f6s Sect. Math. 7 (1964), 143\u2013149.","journal-title":"Ann. Univ. Sci. Budapest, E\u00f6tv\u00f6s Sect. Math."},{"key":"BF02579382_CR17","first-page":"215","volume":"7","author":"P. Erd\u0151s","year":"1962","unstructured":"P. Erd\u0151s andA. R\u00e9nyi, On a problem in the theory of graphs,Publ. Math. Inst. Hungar. Acad. Sci. 7 (1962), 215\u2013235 (in Hungarian).","journal-title":"Publ. Math. Inst. Hungar. Acad. Sci."},{"key":"BF02579382_CR18","unstructured":"P. Frankl, V. R\u0151dl andR. M. Wilson, The number of submatrices of given type in a Hadamard martrix,J. of Combinatorial Theory B, to appear."},{"key":"BF02579382_CR19","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1007\/BF02579457","volume":"1","author":"P. Frankl","year":"1981","unstructured":"P. Frankl andR. M. Wilson, Intersection theorems with geometric consequences,Combinatorica 1 (1981), 357\u2013368.","journal-title":"Combinatorica"},{"key":"BF02579382_CR20","doi-asserted-by":"crossref","first-page":"407","DOI":"10.1016\/0022-0000(81)90040-4","volume":"22","author":"O. Gabber","year":"1981","unstructured":"O. Gabber andZ. Galil, Explicit construction of linear sized superconcentrators,J. Comp. and Sys. Sci. 22 (1981), 407\u2013420.","journal-title":"J. Comp. and Sys. Sci."},{"key":"BF02579382_CR21","volume-title":"Shift Register Sequences","author":"S. Golomb","year":"1967","unstructured":"S. Golomb,Shift Register Sequences, Holden Day, Inc., San Francisco, 1967."},{"key":"BF02579382_CR22","unstructured":"R. K. Guy andS. Znam, A problem of Zarankiewicz, in:Recent Progress in Combinatorics (W. T. Tutte, ed.) Academic Press, 1969, 237\u2013243."},{"key":"BF02579382_CR23","volume-title":"Combinatorial Theory","author":"M. Hall Jr.","year":"1967","unstructured":"M. Hall, Jr.,Combinatorial Theory, Wiley and Sons, New York and London, 1967."},{"key":"BF02579382_CR24","first-page":"497","volume":"29","author":"R. H\u00e4ggkvist","year":"1980","unstructured":"R. H\u00e4ggkvist andP. Hell, Graphs and parallel comparison algorithms.Congr. Num. 29 (1980), 497\u2013509.","journal-title":"Congr. Num."},{"key":"BF02579382_CR25","doi-asserted-by":"crossref","first-page":"465","DOI":"10.1137\/0210034","volume":"10","author":"R. H\u00e4ggkvist","year":"1981","unstructured":"R. H\u00e4ggkvist andP. Hell, Parallel sorting with constant time for comparisons,SIAM J. Comp. 10, (1981), 465\u2013472.","journal-title":"SIAM J. Comp."},{"key":"BF02579382_CR26","doi-asserted-by":"crossref","first-page":"465","DOI":"10.1137\/0603047","volume":"3","author":"R. H\u00e4ggkvist","year":"1982","unstructured":"R. H\u00e4ggkvist andP. Hell, Sorting and merging in rounds,SIAM J. Alg. and Disc. Meth. 3 (1982), 465\u2013473.","journal-title":"SIAM J. Alg. and Disc. Meth."},{"key":"BF02579382_CR27","doi-asserted-by":"crossref","unstructured":"J. Ja\u2019Ja, Time space tradeoffs for some algebraic problems,Proc. 12 th Ann. ACM Symp. on Theory of Computing, 1980, 339\u2013350.","DOI":"10.1145\/800141.804683"},{"key":"BF02579382_CR28","doi-asserted-by":"crossref","unstructured":"M. Klawe, Non-existence of one-dimensional expanding graphs,Proc. 22 nd Ann. Symp. Found. Comp. Sci. Nashville (1981). 109\u2013113.","DOI":"10.1109\/SFCS.1981.23"},{"key":"BF02579382_CR29","doi-asserted-by":"crossref","first-page":"1087","DOI":"10.1145\/322344.322354","volume":"29","author":"T. Lengauer","year":"1982","unstructured":"T. Lengauer andR. E. Tarjan, Asymptotically tight bounds on time space trade-offs in a pebble game,J. ACM 29 (1982), 1087\u20131130.","journal-title":"J. ACM"},{"key":"BF02579382_CR30","first-page":"71","volume":"9","author":"G. A. Margulis","year":"1973","unstructured":"G. A. Margulis, Explicit constructions of concentrators,Prob. Per. Infor. 9 (1973), 71\u201380, (English translation inProblems of Infor. Trans. (1975), 325\u2013332).","journal-title":"Prob. Per. Infor."},{"key":"BF02579382_CR31","unstructured":"R. Meshuluam, A geometric construction of a superconcentrator of depth 2,preprint."},{"key":"BF02579382_CR32","unstructured":"M. Pinsker, On the complexity of a concentrator,7th International Teletraffic Conference, Stockholm, June 1973, 318\/1\u2013318\/4."},{"key":"BF02579382_CR33","doi-asserted-by":"crossref","first-page":"298","DOI":"10.1137\/0206022","volume":"6","author":"N. Pippenger","year":"1977","unstructured":"N. Pippenger, Superconcentrators,SIAM J. Computing 6 (1977), 298\u2013304.","journal-title":"SIAM J. Computing"},{"key":"BF02579382_CR34","first-page":"407","volume":"9","author":"N. Pippenger","year":"1982","unstructured":"N. Pippenger, Advances in pebbling, Internat.Colloq. on Autom. Lang. and Prog. 9 (1982), 407\u2013417.","journal-title":"Colloq. on Autom. Lang. and Prog."},{"key":"BF02579382_CR35","unstructured":"N. Pippenger, Explicit construction of highly expanding graphs,preprint."},{"key":"BF02579382_CR36","first-page":"239","volume":"20","author":"W. J. Paul","year":"1977","unstructured":"W. J. Paul, R. E. Tarjan andJ. R. Celoni, Space bounds for a game on graphs,Math. Sys. Theory 20 (1977), 239\u2013251.","journal-title":"Math. Sys. Theory"},{"key":"BF02579382_CR37","volume-title":"Final report to office of environmental education","author":"S. Scheele","year":"1977","unstructured":"S. Scheele,Final report to office of environmental education. Dept. of Health, Education and Welfare, Social Engineering Technology, Los Angeles, CA 1977."},{"key":"BF02579382_CR38","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1016\/0012-365X(77)90044-9","volume":"20","author":"J. Spencer","year":"1977","unstructured":"J. Spencer, Asymtotic lower bounds for Ramsey functions,Discrete Math. 20 (1977), 69\u201376.","journal-title":"Discrete Math."},{"key":"BF02579382_CR39","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1137\/0605030","volume":"5","author":"R. M. Tanner","year":"1984","unstructured":"R. M. Tanner, Explicit construction of concentrators from generalizedN-gons,SIAM J. Alg. Discr. Meth.,5 (1984), 287\u2013293.","journal-title":"SIAM J. Alg. Discr. Meth."},{"key":"BF02579382_CR40","doi-asserted-by":"crossref","first-page":"118","DOI":"10.1016\/0022-0000(80)90056-2","volume":"20","author":"M. Tompa","year":"1980","unstructured":"M. Tompa, Time space tradeoffs for computing functions, using connectivity properties of their circuits,J. Comp. and Sys. Sci. 20 (1980), 118\u2013132.","journal-title":"J. Comp. and Sys. Sci."},{"key":"BF02579382_CR41","doi-asserted-by":"crossref","first-page":"348","DOI":"10.1137\/0204030","volume":"4","author":"L. G. Valiant","year":"1975","unstructured":"L. G. Valiant, Paralelism in comparison networks.SIAM J. Comp. 4 (1975), 348\u2013355.","journal-title":"SIAM J. Comp."},{"key":"BF02579382_CR42","doi-asserted-by":"crossref","first-page":"278","DOI":"10.1016\/S0022-0000(76)80041-4","volume":"13","author":"L. G. Valiant","year":"1976","unstructured":"L. G. Valiant, Graph theoretic properties in computational complexity,J. Com. and Sys. Sci. 13 (1976), 278\u2013285.","journal-title":"J. Com. and Sys. Sci."},{"key":"BF02579382_CR43","unstructured":"N. Alon, Y. Azar, andU. Vizhkin, Tight complexity bounds for parallel comparison sorting,Proc. 27th FOCS, to appear."},{"key":"BF02579382_CR44","unstructured":"A. Lubotzky, R. Phillips, andP. Sarnak, Ramanujan graphs,to appear."},{"key":"BF02579382_CR45","unstructured":"N. Pippenger, Sorting and selecting in rounds,preprint."}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02579382.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02579382\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02579382","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,15]],"date-time":"2025-01-15T05:13:46Z","timestamp":1736918026000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02579382"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1986,9]]},"references-count":45,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1986,9]]}},"alternative-id":["BF02579382"],"URL":"https:\/\/doi.org\/10.1007\/bf02579382","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[1986,9]]}}}