{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T03:19:14Z","timestamp":1775618354967,"version":"3.50.1"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2021,2,1]],"date-time":"2021-02-01T00:00:00Z","timestamp":1612137600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,2,1]],"date-time":"2021-02-01T00:00:00Z","timestamp":1612137600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2021,8]]},"DOI":"10.1007\/s00493-020-4429-x","type":"journal-article","created":{"date-parts":[[2021,2,1]],"date-time":"2021-02-01T17:05:53Z","timestamp":1612199153000},"page":"447-463","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":26,"title":["Explicit Expanders of Every Degree and Size"],"prefix":"10.1007","volume":"41","author":[{"given":"Noga","family":"Alon","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,2,1]]},"reference":[{"key":"4429_CR1","doi-asserted-by":"publisher","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":"4429_CR2","doi-asserted-by":"crossref","unstructured":"N. Alon and F. R. K. Chung: Explicit construction of linear sized tolerant networks, Discrete Math. 72 (1988), 15\u201319; (Proc. of the First Japan Conference on Graph Theory and Applications, Hakone, Japan, 1986.)","DOI":"10.1016\/S0167-5060(08)70766-0"},{"key":"4429_CR3","unstructured":"N. Alon, S. Ganguly and N. Srivastava: High-girth near-Ramanujan graphs with localized eigenvectors, Israel J. Math., to appear, arXiv:1908.03694, 2019."},{"key":"4429_CR4","doi-asserted-by":"publisher","first-page":"532","DOI":"10.1112\/plms\/83.3.532","volume":"83","author":"R C Baker","year":"2001","unstructured":"R. C. Baker, G. Harman and J. Pintz: The difference between consecutive primes II., Proc. London Math. Soc. 83 (2001), 532\u2013562.","journal-title":"Proc. London Math. Soc."},{"key":"4429_CR5","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1137\/080732651","volume":"40","author":"A Ben-Aroya","year":"2011","unstructured":"A. Ben-Aroya and A. Ta-Shma: A combinatorial construction of almost Ramanujan graphs using the zig-zag product, SIAM Journal on Computing 40 (2011), 267\u2013290.","journal-title":"SIAM Journal on Computing"},{"key":"4429_CR6","unstructured":"C. Bordenave: A new proof of Friedman\u2019s second eigenvalue theorem and its extension to random lifts, To appear in Annales scientifiques de l\u00c9cole normale sup\u00e9rieure, arXiv:1502.04482v4, 2019."},{"key":"4429_CR7","doi-asserted-by":"publisher","first-page":"745","DOI":"10.1515\/FORUM.2008.035","volume":"20","author":"S M Cioab\u0103","year":"2008","unstructured":"S. M. Cioab\u0103 and M. Ram Murty: Expander graphs and gaps between primes, Forum Mathematicum 20 (2008), 745\u2013756.","journal-title":"Forum Mathematicum"},{"key":"4429_CR8","doi-asserted-by":"crossref","unstructured":"M. Cohen: Ramanujan graphs in polynomial time, in: Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science, 276\u2013281, 2016.","DOI":"10.1109\/FOCS.2016.37"},{"key":"4429_CR9","doi-asserted-by":"publisher","first-page":"487","DOI":"10.1215\/S0012-7094-93-06921-9","volume":"69","author":"J Friedman","year":"1993","unstructured":"J. Friedman: Some geometric aspects of graphs and their eigenfunctions, Duke Mathematical Journal 69 (1993), 487\u2013525.","journal-title":"Duke Mathematical Journal"},{"key":"4429_CR10","doi-asserted-by":"publisher","first-page":"viii+100","DOI":"10.1090\/memo\/0910","volume":"195","author":"J Friedman","year":"2008","unstructured":"J. Friedman: A proof of Alon\u2019s second eigenvalue conjecture and related problems, Memoirs of the American Mathematical Society 195 (2008), viii+100.","journal-title":"Memoirs of the American Mathematical Society"},{"key":"4429_CR11","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1112\/plms\/s3-64.2.265","volume":"64","author":"D R Heath-Brown","year":"1992","unstructured":"D. R. Heath-Brown: Zero-free regions for Dirichlet L-functions, and the least prime in an arithmetic progression, Proc. London Math. Soc. (3) 64 (1992), 265\u2013338.","journal-title":"Proc. London Math. Soc. (3)"},{"key":"4429_CR12","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1090\/S0273-0979-06-01126-8","volume":"43","author":"S Hoory","year":"2006","unstructured":"S. Hoory, N. Linial and A. Wigderson: Expander graphs and their applications, Bull. Amer. Math. Soc. (N.S.) 43 (2006), 439\u2013561.","journal-title":"Bull. Amer. Math. Soc. (N.S.)"},{"key":"4429_CR13","doi-asserted-by":"publisher","first-page":"1091","DOI":"10.1145\/210118.210136","volume":"42","author":"N Kahale","year":"1995","unstructured":"N. Kahale: Eigenvalues and expansion of regular graphs, Journal of the ACM 42 (1995), 1091\u20131106.","journal-title":"Journal of the ACM"},{"key":"4429_CR14","first-page":"199","volume-title":"Bolyai Soc. Math. Stud., 15","author":"M Krivelevich","year":"2006","unstructured":"M. Krivelevich and B. Sudakov: Pseudo-random graphs, in: More sets, graphs and numbers, 199\u2013262, Bolyai Soc. Math. Stud., 15, Springer, Berlin, 2006."},{"key":"4429_CR15","unstructured":"A. Lubotzky: Discrete Groups, Expanding Graphs and Invariant Measures, Springer 2010"},{"key":"4429_CR16","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1007\/BF02126799","volume":"8","author":"A Lubotzky","year":"1988","unstructured":"A. Lubotzky, R. Phillips and P. Sarnak: Ramanujan graphs, Combinatorica 8 (1988), 261\u2013277.","journal-title":"Combinatorica"},{"key":"4429_CR17","first-page":"51","volume":"24","author":"G A Margulis","year":"1988","unstructured":"G. A. Margulis: Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and superconcentrators, Problemy Peredachi Informatsii 24 (1988), 51\u201360 (in Russian). English translation in Problems of Information Transmission 24 (1988), 39\u201346.","journal-title":"Problemy Peredachi Informatsii"},{"key":"4429_CR18","unstructured":"S. Mohanty, R. O\u2019Donnell and P. Paredes: Explicit near-Ramanujan graphs of every degree, arXiv:1909.06988v2."},{"key":"4429_CR19","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1006\/jctb.1994.1054","volume":"62","author":"M Morgenstern","year":"1994","unstructured":"M. Morgenstern: Existence and explicit constructions of q + 1 regular Ramanujan graphs for every prime power q, Journal of Combinatorial Theory, Series B 62 (1994), 44\u201362.","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"4429_CR20","doi-asserted-by":"publisher","first-page":"307","DOI":"10.4007\/annals.2015.182.1.7","volume":"182","author":"A Marcus","year":"2015","unstructured":"A. Marcus, D. Spielman and N. Srivastava: Interlacing families I: Bipartite Ramanujan graphs of all degrees, Annals of Mathematics, Second Series 182 (2015), 307\u2013325.","journal-title":"Annals of Mathematics, Second Series"},{"key":"4429_CR21","first-page":"1","volume":"42","author":"J Murtagh","year":"2019","unstructured":"J. Murtagh, O. Reingold, A. Sidford and S. Vadhan: Deterministic Approximation of Random Walks in Small Space, Proc. APPROX-RANDOM 42 (2019), 1\u201322.","journal-title":"Proc. APPROX-RANDOM"},{"key":"4429_CR22","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1016\/0012-365X(91)90112-F","volume":"91","author":"A Nilli","year":"1991","unstructured":"A. Nilli: On the second eigenvalue of a graph, Discrete Mathematics 91 (1991), 207\u2013210.","journal-title":"Discrete Mathematics"},{"key":"4429_CR23","doi-asserted-by":"publisher","first-page":"157","DOI":"10.2307\/3062153","volume":"155","author":"O Reingold","year":"2002","unstructured":"O. Reingold, S. Vadhan and A. Wigderson: Entropy waves, the zig-zag graph product, and new constant-degree expanders, Annals of Mathematics 155 (2002), 157\u2013187.","journal-title":"Annals of Mathematics"},{"key":"4429_CR24","unstructured":"M. Sha, E. Shparlinski and C. L. Stewart: On the distribution of multiplicatively dependenet vectors, arXiv:1903.09796."},{"key":"4429_CR25","first-page":"159","volume":"28","author":"R Tijdeman","year":"1974","unstructured":"R. Tijdeman: On the maximal distance between integers composed of small primes, Compos. Math. 28 (1974), 159\u2013162.","journal-title":"Compos. Math."}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-020-4429-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00493-020-4429-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-020-4429-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,20]],"date-time":"2021-10-20T21:14:22Z","timestamp":1634764462000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00493-020-4429-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,2,1]]},"references-count":25,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,8]]}},"alternative-id":["4429"],"URL":"https:\/\/doi.org\/10.1007\/s00493-020-4429-x","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,2,1]]},"assertion":[{"value":"26 January 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 October 2020","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 February 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}