{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,14]],"date-time":"2026-04-14T17:37:43Z","timestamp":1776188263996,"version":"3.50.1"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[1986,6,1]],"date-time":"1986-06-01T00:00:00Z","timestamp":517968000000},"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,6]]},"DOI":"10.1007\/bf02579166","type":"journal-article","created":{"date-parts":[[2007,3,22]],"date-time":"2007-03-22T21:15:33Z","timestamp":1174598133000},"page":"83-96","source":"Crossref","is-referenced-by-count":646,"title":["Eigenvalues and expanders"],"prefix":"10.1007","volume":"6","author":[{"given":"Noga","family":"Alon","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"BF02579166_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":"BF02579166_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\u201319.","journal-title":"Combinatorica"},{"key":"BF02579166_CR3","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":"BF02579166_CR4","doi-asserted-by":"crossref","unstructured":"N. Alon andV. D. Milman, Eigenvalues, expanders and superconcentrators,Proc. 25 th Ann. Symp. on Foundations of Comp. Sci., Florida (1984), 320\u2013322.","DOI":"10.1109\/SFCS.1984.715931"},{"key":"BF02579166_CR5","unstructured":"N. Alon, Z. Galil andV. D. Milman, Better expanders and superconcentrators,to appear."},{"key":"BF02579166_CR6","unstructured":"W. N. Anderson, Jr. andT. D. Morley, Eigenvalues of the Laplacian of a graph,University of Maryland Technical Report TR-71-45, (1971)."},{"key":"BF02579166_CR7","first-page":"206","volume":"17","author":"L. A. Bassalygo","year":"1981","unstructured":"L. A. Bassalygo, Asymptotically optimal switching circuits,Problems of Infor. Trans. 17 (1981), 206\u2013211.","journal-title":"Problems of Infor. Trans."},{"key":"BF02579166_CR8","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511608704","volume-title":"Algebraic Graph Theory","author":"N. Biggs","year":"1974","unstructured":"N. Biggs,Algebraic Graph Theory, Cambridge University Press, London, 1974."},{"key":"BF02579166_CR9","doi-asserted-by":"crossref","first-page":"164","DOI":"10.1016\/0020-0190(81)90050-8","volume":"13","author":"M. Blum","year":"1981","unstructured":"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\u2013167.","journal-title":"Inform. Process. Letters"},{"key":"BF02579166_CR10","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1016\/S0195-6698(80)80030-8","volume":"1","author":"B. Bollob\u00e1s","year":"1980","unstructured":"B. Bollob\u00e1s, A. probabilistic proof of an asymptotic formula for the number of labelled regular graphs,Europ. J. Combinatorics 1 (1980), 311\u2013316.","journal-title":"Europ. J. Combinatorics"},{"key":"BF02579166_CR11","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1007\/BF01437826","volume":"162","author":"P. Buser","year":"1978","unstructured":"P. Buser, Cubic graphs and the first eigenvalue of a Riemann surface,Math. Z. 162 (1978), 87\u201399.","journal-title":"Math. Z."},{"key":"BF02579166_CR12","first-page":"195","volume-title":"Problems in Analysis","author":"J. Cheeger","year":"1970","unstructured":"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\u2013199."},{"key":"BF02579166_CR13","doi-asserted-by":"crossref","first-page":"1765","DOI":"10.1002\/j.1538-7305.1979.tb02972.x","volume":"58","author":"F. K. R. Chung","year":"1978","unstructured":"F. K. R. Chung, On concentrators, superconcentrators, generalizers and nonblocking networks,Bell Sys. Tech. J. 58 (1978), 1765\u20131777.","journal-title":"Bell Sys. Tech. J."},{"key":"BF02579166_CR14","first-page":"47","volume-title":"Algebraic Methods in Graph Theory","author":"D. M. Cvetkovic","year":"1981","unstructured":"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\u00e1sz and V. T. S\u00f3s eds.), North-Holland, Amsterdam, (1981) 47\u201367."},{"key":"BF02579166_CR15","doi-asserted-by":"crossref","unstructured":"M. Fiedler, Algebraic connectivity of graphs,Czechoslovak. Math. J. 23 (98), (1973), 298\u2013305.","DOI":"10.21136\/CMJ.1973.101168"},{"key":"BF02579166_CR16","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1007\/BF02579329","volume":"1","author":"Z. F\u00fcredi","year":"1981","unstructured":"Z. F\u00fcredi andJ. Koml\u00f3s, The eigenvalues of random symmetric matrices,Combinatorica 1 (1981), 233\u2013241.","journal-title":"Combinatorica"},{"key":"BF02579166_CR17","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":"BF02579166_CR18","doi-asserted-by":"crossref","first-page":"843","DOI":"10.2307\/2374298","volume":"105","author":"M. Gromov","year":"1983","unstructured":"M. Gromov andV. D. Milman, A topological application of the isoperimetric inequality,American J. Math. 105 (1983), 843\u2013854.","journal-title":"American J. Math."},{"key":"BF02579166_CR19","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":"BF02579166_CR20","doi-asserted-by":"crossref","unstructured":"S. Jimbo andA. Maruoka, Expanders obtained from affine transformations (extended abstract),preprint (1984).","DOI":"10.1145\/22145.22155"},{"key":"BF02579166_CR21","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 tradeoffs in a pebble game,J. ACM 29 (1982), 1087\u20131130.","journal-title":"J. ACM"},{"key":"BF02579166_CR22","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":"BF02579166_CR23","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1016\/0024-3795(81)90150-6","volume":"40","author":"B. D. McKay","year":"1981","unstructured":"B. D. McKay, The expected eigenvalue distribution of a large regular graph,Linear Algebra Appl. 40 (1981), 203\u2013216.","journal-title":"Linear Algebra Appl."},{"key":"BF02579166_CR24","unstructured":"M. Pinkser, On the complexity of a concentrator,7 th International Teletraffic Conference, Stockholm, June 1973, 318\/1\u2013318\/4."},{"key":"BF02579166_CR25","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":"BF02579166_CR26","first-page":"407","volume":"9","author":"N. Pippenger","year":"1982","unstructured":"N. Pippenger, Advances in pebbling,Internat. Colloq. on Autom., Langs. and Prog. 9 (1982), 407\u2013417.","journal-title":"Internat. Colloq. on Autom., Langs. and Prog."},{"key":"BF02579166_CR27","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1007\/BF01683275","volume":"10","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 10 (1977), 239\u2013251.","journal-title":"Math. Sys. Theory"},{"key":"BF02579166_CR28","unstructured":"A. Ralston,A First Course in Numerical Analysis, McGraw-Hill, 1985, Section 10.4."},{"key":"BF02579166_CR29","first-page":"286","volume-title":"Proc. of a Workshop on Graph Theoretic Concepts in Computer Science","author":"A. L. Rosenberg","year":"1983","unstructured":"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\u2013297."},{"key":"BF02579166_CR30","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":"BF02579166_CR31","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":"BF02579166_CR32","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. Comp. and Sys. Sci. 13 (1976), 278\u2013285.","journal-title":"J. Comp. and Sys. Sci."},{"key":"BF02579166_CR33","doi-asserted-by":"crossref","first-page":"325","DOI":"10.2307\/1970008","volume":"67","author":"E. P. Wigner","year":"1958","unstructured":"E. P. Wigner, On the distribution of the roots of certain symmetric matrices,Ann. Math. 67 (1958), 325\u2013327.","journal-title":"Ann. Math."},{"key":"BF02579166_CR34","unstructured":"A. Lubotzky, R. Phillips, andP. Sarnak, Ramanujan graphs,to appear."}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02579166.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02579166\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02579166","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,15]],"date-time":"2025-01-15T05:06:07Z","timestamp":1736917567000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02579166"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1986,6]]},"references-count":34,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1986,6]]}},"alternative-id":["BF02579166"],"URL":"https:\/\/doi.org\/10.1007\/bf02579166","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[1986,6]]}}}