{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,18]],"date-time":"2026-05-18T13:50:56Z","timestamp":1779112256709,"version":"3.51.4"},"reference-count":30,"publisher":"Wiley","issue":"2","license":[{"start":{"date-parts":[[2006,10,11]],"date-time":"2006-10-11T00:00:00Z","timestamp":1160524800000},"content-version":"vor","delay-in-days":4576,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Random Struct Algorithms"],"published-print":{"date-parts":[[1994,4]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>For every 1 &gt; \u03b4 &gt; 0 there exists a<jats:italic>c<\/jats:italic>=<jats:italic>c<\/jats:italic>(\u03b4) &gt; 0 such that for every group<jats:italic>G<\/jats:italic>of order<jats:italic>n<\/jats:italic>, and for a set<jats:italic>S<\/jats:italic>of<jats:italic>c<\/jats:italic>(\u03b4) log<jats:italic>n<\/jats:italic>random elements in the group, the expected value of the second largest eigenvalue of the normalized adjacency matrix of the Cayley graph<jats:italic>X(G, S)<\/jats:italic>is at most (1 \u2010 \u03b4). This implies that almost every such a graph is an \u03f5(\u03b4)\u2010expander. For Abelian groups this is essentially tight, and explicit constructions can be given in some cases. \u00a9 1994 John Wiley &amp; Sons, Inc.<\/jats:p>","DOI":"10.1002\/rsa.3240050203","type":"journal-article","created":{"date-parts":[[2007,6,1]],"date-time":"2007-06-01T20:52:51Z","timestamp":1180731171000},"page":"271-284","source":"Crossref","is-referenced-by-count":139,"title":["Random Cayley graphs and expanders"],"prefix":"10.1002","volume":"5","author":[{"given":"Noga","family":"Alon","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuval","family":"Roichman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1112\/blms\/22.6.583"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579166"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579382"},{"key":"e_1_2_1_5_2","unstructured":"N.Alon A.Barak andU.Manber On disseminating information reliably without broadcasting Proc. of the 7th International Conference on Distributed Computing Systems (ICDS) Berlin Germany September1987 pp.74\u201381."},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1109\/18.119713"},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(85)90092-9"},{"key":"e_1_2_1_7_3","first-page":"320","volume-title":"Proc. 25th IEEE FOCS","author":"Alon N.","year":"1984"},{"key":"e_1_2_1_8_2","first-page":"544","volume-title":"Proc. 31st IEEE FOCS","author":"Alon N.","year":"1990"},{"key":"e_1_2_1_8_3","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240030308"},{"key":"e_1_2_1_9_2","volume-title":"The Probabilistic Method","author":"Alon N.","year":"1991"},{"key":"e_1_2_1_10_2","first-page":"164","volume-title":"Proc. 23rd Annual ACM STOC","author":"Babai L.","year":"1991"},{"key":"e_1_2_1_11_2","first-page":"27","article-title":"Representation of group elements as short products","volume":"12","author":"Babai L.","year":"1982","journal-title":"Ann. Discrete Math."},{"key":"e_1_2_1_12_2","doi-asserted-by":"crossref","unstructured":"L.Babai G.Hetyei W. M.Kantor A.Lubotzky andA.Seress On the diameter of finite groups Proc. 31st IEEE FOCS IEEE 1990 pp.857\u2013865.","DOI":"10.1109\/FSCS.1990.89608"},{"key":"e_1_2_1_13_2","doi-asserted-by":"crossref","unstructured":"A.BroderandE.Shamir On the second eigenvalue of random regular graphs Proc. 28th IEEE FOCS IEEE 1987 pp.286\u2013294.","DOI":"10.1109\/SFCS.1987.45"},{"key":"e_1_2_1_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01275669"},{"key":"e_1_2_1_15_2","doi-asserted-by":"publisher","DOI":"10.1215\/S0012-7094-93-06921-9"},{"key":"e_1_2_1_16_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579329"},{"key":"e_1_2_1_17_2","first-page":"587","volume-title":"Proc. 21st ACM STOC","author":"Friedman J.","year":"1989"},{"key":"e_1_2_1_18_2","first-page":"296","volume-title":"Proc. 33rd Annual IEEE FOCS","author":"Kahale N.","year":"1992"},{"key":"e_1_2_1_19_2","volume-title":"Combinatorial Problems and Exercises","author":"Lov\u00e1sz L.","year":"1979"},{"key":"e_1_2_1_20_2","author":"Lubotzky A.","journal-title":"Discrete Groups, Expanding Graphs and Invariant Measures"},{"key":"e_1_2_1_21_2","doi-asserted-by":"crossref","unstructured":"A.Lubotzky R.Phillips andP.Sarnak Explicit expanders and the Ramanujan conjectures Proc. 18th ACM STOC 1986 pp.240\u2013246.","DOI":"10.1145\/12130.12154"},{"key":"e_1_2_1_21_3","first-page":"261","volume":"8","author":"Lubotzky A.","year":"1988","journal-title":"Ramanujan graphs, Combinatorica"},{"key":"e_1_2_1_22_2","first-page":"51","article-title":"Explicit group\u2010theoretical constructions of combinatorial schemes and their application to the design of expanders and superconcentrators","volume":"24","author":"Margulis G. A.","year":"1988","journal-title":"Prob. Perecachi Inf."},{"key":"e_1_2_1_22_3","first-page":"39","volume":"24","year":"1988","journal-title":"Probl. Inf. Transm."},{"key":"e_1_2_1_23_2","volume-title":"The Theory of Error\u2010Correcting Codes","author":"MacWilliams F. J.","year":"1977"},{"key":"e_1_2_1_24_2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(91)90112-F"},{"key":"e_1_2_1_25_2","doi-asserted-by":"publisher","DOI":"10.1137\/0605030"},{"key":"e_1_2_1_26_2","doi-asserted-by":"publisher","DOI":"10.2307\/1970079"},{"key":"e_1_2_1_27_2","doi-asserted-by":"publisher","DOI":"10.2307\/1970008"}],"container-title":["Random Structures &amp; Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Frsa.3240050203","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/rsa.3240050203","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,16]],"date-time":"2025-01-16T21:26:37Z","timestamp":1737062797000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/rsa.3240050203"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,4]]},"references-count":30,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1994,4]]}},"alternative-id":["10.1002\/rsa.3240050203"],"URL":"https:\/\/doi.org\/10.1002\/rsa.3240050203","archive":["Portico"],"relation":{},"ISSN":["1042-9832","1098-2418"],"issn-type":[{"value":"1042-9832","type":"print"},{"value":"1098-2418","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994,4]]}}}