{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T00:27:08Z","timestamp":1761611228796},"reference-count":29,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2008,9,12]],"date-time":"2008-09-12T00:00:00Z","timestamp":1221177600000},"content-version":"unspecified","delay-in-days":6039,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[1992,3]]},"abstract":"<jats:p>A graph is vertex-transitive (edge-transitive) if its automorphism group acts transitively on the vertices (edges, resp.). The<jats:italic>expansion rate<\/jats:italic>of a subset<jats:italic>S<\/jats:italic>of the vertex set is the quotient e(S):= |\u2202(S)|\/|<jats:italic>S<\/jats:italic>|, where \u2202(<jats:italic>S<\/jats:italic>) denotes the set of vertices not in<jats:italic>S<\/jats:italic>but adjacent to some vertex in<jats:italic>S<\/jats:italic>. Improving and extending previous results of Aldous and Babai, we give very simple proofs of the following results. Let<jats:italic>X<\/jats:italic>be a (finite or infinite) vertex-transitive graph and let<jats:italic>S<\/jats:italic>be a finite subset of the vertices. If<jats:italic>X<\/jats:italic>is finite, we also assume |<jats:italic>S<\/jats:italic>| \u2264|<jats:italic>V<\/jats:italic>(<jats:italic>X<\/jats:italic>)\/2. Let<jats:italic>d<\/jats:italic>be the diameter of<jats:italic>S<\/jats:italic>in the metric induced by<jats:italic>X<\/jats:italic>. Then e(S) \u22651\/(<jats:italic>d<\/jats:italic>+ 1); and<jats:italic>e(S)<\/jats:italic>\u2265 2\/(<jats:italic>d<\/jats:italic>+2) if<jats:italic>X<\/jats:italic>is finite and<jats:italic>d<\/jats:italic>is less than the diameter of<jats:italic>X<\/jats:italic>. If<jats:italic>X<\/jats:italic>is edge-transitive then |\u03b4(<jats:italic>S<\/jats:italic>)|\/|<jats:italic>S<\/jats:italic>| \u2265<jats:italic>r<\/jats:italic>\/(2<jats:italic>d<\/jats:italic>), where \u2202(<jats:italic>S<\/jats:italic>) denotes the set of edges joining<jats:italic>S<\/jats:italic>to its complement and<jats:italic>r<\/jats:italic>is the harmonic mean of the minimum and maximum degrees of<jats:italic>X<\/jats:italic>. \u2013 Diverse applications of the results are mentioned.<\/jats:p>","DOI":"10.1017\/s0963548300000031","type":"journal-article","created":{"date-parts":[[2008,9,12]],"date-time":"2008-09-12T11:19:46Z","timestamp":1221218386000},"page":"1-11","source":"Crossref","is-referenced-by-count":26,"title":["Local Expansion of Symmetrical Graphs"],"prefix":"10.1017","volume":"1","author":[{"given":"L\u00e1szl\u00f3","family":"Babai","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mario","family":"Szegedy","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2008,9,12]]},"reference":[{"key":"S0963548300000031_ref004","unstructured":"[4] Babai L. . Bounded-round interactive proofs in finite groups. SIAM J. Discr. Math., to appear."},{"key":"S0963548300000031_ref013","volume-title":"Random Graphs","author":"Bollob\u00e1s","year":"1985"},{"key":"S0963548300000031_ref002","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(85)90092-9"},{"key":"S0963548300000031_ref028","first-page":"203","article-title":"Th\u00e9orie du potential sur les groupes et des vari\u00e9t\u00e9s","volume":"302","author":"Varopoulos","year":"1986","journal-title":"Comptes Rendus Acad. Sci. Paris"},{"key":"S0963548300000031_ref024","doi-asserted-by":"publisher","DOI":"10.1007\/BF01222585"},{"key":"S0963548300000031_ref025","article-title":"Explicit group theoretic constructions of combinatorial schemes and their applications for the construction of expanders and concentrators (in Russian)","author":"Margulis","year":"1988","journal-title":"J. Probl. Info. Transmission"},{"key":"S0963548300000031_ref008","unstructured":"[8] Babai L. . Automorphism group, isomorphism, reconstruction: Chapter 27 in [18]."},{"key":"S0963548300000031_ref020","doi-asserted-by":"publisher","DOI":"10.1016\/S0021-9800(66)80059-5"},{"key":"S0963548300000031_ref019","doi-asserted-by":"publisher","DOI":"10.1007\/BF02698687"},{"key":"S0963548300000031_ref014","volume-title":"Combinatorics","author":"Bollob\u00e1s","year":"1986"},{"key":"S0963548300000031_ref005","first-page":"164","volume-title":"In Proc. 23rd ACM Symp. Theory of Computing","author":"Babai","year":"1991"},{"key":"S0963548300000031_ref022","volume-title":"Combinatorial Problems and Exercises","author":"Lov\u00e1sz","year":"1979"},{"key":"S0963548300000031_ref017","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(81)90009-1"},{"key":"S0963548300000031_ref010","doi-asserted-by":"crossref","first-page":"200","DOI":"10.1145\/120694.120724","article-title":"Nearly linear time algorithms for permutation groups with a small base","author":"Babai","year":"1991","journal-title":"In Proc. ISSAC'91 (Internat. Symp. on Symbolic and Algebraic Computation)"},{"key":"S0963548300000031_ref011","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200056"},{"key":"S0963548300000031_ref015","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(91)90022-9"},{"key":"S0963548300000031_ref006","unstructured":"[6] Babai L. . Deciding finiteness of matrix groups in Las Vegas polynomial time. In Proc. 3rd ACM-SIAM Symp. on Discrete Algorithms, Orlando FL 1992, pp. 33\u201340."},{"key":"S0963548300000031_ref018","volume-title":"Handbook of Combinatorics","author":"Graham"},{"key":"S0963548300000031_ref029","doi-asserted-by":"publisher","DOI":"10.1016\/S0021-9800(70)80005-9"},{"key":"S0963548300000031_ref012","first-page":"21","volume-title":"In Proc. 23rd ACM Symp. Theory of Computing","author":"Babai","year":"1991"},{"key":"S0963548300000031_ref001","doi-asserted-by":"publisher","DOI":"10.1017\/S0269964800000267"},{"key":"S0963548300000031_ref021","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(76)90058-3"},{"key":"S0963548300000031_ref026","doi-asserted-by":"publisher","DOI":"10.1112\/blms\/21.3.209"},{"key":"S0963548300000031_ref016","first-page":"2","article-title":"Approximating clique is almost NP-complete","author":"Feige","year":"1991","journal-title":"In Proc. 32nd IEEE Conf. Found. Comp. Sci."},{"key":"S0963548300000031_ref007","volume-title":"Proc. International Congress of Mathematicians","author":"Babai","year":"1990"},{"key":"S0963548300000031_ref003","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190090308"},{"key":"S0963548300000031_ref009","doi-asserted-by":"crossref","unstructured":"[9] Babai L. , Beals R. M. and Rockmore D. . Deciding finiteness of matrix groups in polynomial time. Manuscript, 1992.","DOI":"10.1145\/164081.164104"},{"key":"S0963548300000031_ref023","doi-asserted-by":"publisher","DOI":"10.1007\/BF02126799"},{"key":"S0963548300000031_ref027","doi-asserted-by":"publisher","DOI":"10.1016\/0022-1236(85)90086-2"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548300000031","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,19]],"date-time":"2023-05-19T22:55:48Z","timestamp":1684536948000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548300000031\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992,3]]},"references-count":29,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1992,3]]}},"alternative-id":["S0963548300000031"],"URL":"https:\/\/doi.org\/10.1017\/s0963548300000031","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[1992,3]]}}}