{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:47:28Z","timestamp":1787320048581,"version":"build-2736575974"},"reference-count":36,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","funder":[{"DOI":"10.13039\/501100001742","name":"United States-Israel Binational Science Foundation","doi-asserted-by":"publisher","award":["2014361"],"award-info":[{"award-number":["2014361"]}],"id":[{"id":"10.13039\/501100001742","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1261\/17"],"award-info":[{"award-number":["1261\/17"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>We show that every locally sparse graph contains a linearly sized expanding subgraph. For constants c_1&gt;c_2&gt;1, 0&lt;\\alpha&lt;1, a graph G on n vertices is called a (\\c_1,c_2,\\alpha)-graph if it has at least c_1n edges, but every vertex subset W\\subset V(G) of size |W|\u0142e \\alpha n spans less than c_2|W| edges. We prove that every (c_1,c_2,\\alpha)-graph with bounded degrees contains an induced expander on linearly many vertices. The proof can be made algorithmic. We then discuss several applications of our main result to random graphs, to problems about embedding graph minors, and to positional games.<\/jats:p>","DOI":"10.1137\/17m1128721","type":"journal-article","created":{"date-parts":[[2018,3,1]],"date-time":"2018-03-01T17:12:20Z","timestamp":1519924340000},"page":"611-623","source":"Crossref","is-referenced-by-count":9,"title":["Finding and Using Expanders in Locally Sparse Graphs"],"prefix":"10.1137","volume":"32","author":[{"given":"Michael","family":"Krivelevich","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,3,1]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579166"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(85)90092-9"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-1990-1065053-0"},{"key":"atypb4","unstructured":"N. Alon and J. H. Spencer,\n                      The Probabilistic Method\n                      , 4th ed., Wiley, New York, 2015."},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1145\/2775105"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1007\/BF01897304"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1007\/s004930200009"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2003.12.015"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548315000310"},{"key":"atypb10","first-page":"331","author":"Chung F.","year":"2010","journal-title":"RI"},{"key":"atypb11","doi-asserted-by":"crossref","unstructured":"F. R. K. Chung,\n                      Spectral Graph Theory\n                      , CBMS Regional Conf. Ser. in Math. 92, AMS, Providence, RI, 1997.","DOI":"10.1090\/cbms\/092"},{"key":"atypb12","doi-asserted-by":"crossref","first-page":"4","DOI":"10.37236\/6039","volume":"23","author":"Dean O.","year":"2016","journal-title":"Electron. J. Combin."},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2013.06.004"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1984-0743744-X"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20215"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1007\/s004930050060"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1137\/060654414"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2009.05.001"},{"key":"atypb19","doi-asserted-by":"crossref","unstructured":"D. Hefetz, M. Krivelevich, M. Stojakovic\u0301, and T. Szabo\u0301,\n                      Positional Games\n                      , Birkha\u0308user, Basel, 2014.","DOI":"10.1007\/978-3-0348-0825-5"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2015.12.020"},{"key":"atypb21","first-page":"439","volume":"43","author":"Hoory S.","year":"2006","journal-title":"S.)"},{"key":"atypb22","doi-asserted-by":"crossref","unstructured":"S. Janson, T. \u0141 uczak, and A. Rucin\u0301ski,\n                      Random Graphs\n                      , Wiley, New York, 2000.","DOI":"10.1002\/9781118032718"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1145\/990308.990313"},{"key":"atypb24","doi-asserted-by":"crossref","unstructured":"K. Kawarabayashi and B. Reed,\n                      A separator theorem in minor-closed classes\n                      , in Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS'10), 2010, pp. 153-162.","DOI":"10.1109\/FOCS.2010.22"},{"key":"atypb25","doi-asserted-by":"crossref","unstructured":"J. Kleinberg and R. Rubinfeld,\n                      Short paths in expander graphs\n                      , in Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science (FOCS'96), 1996, pp. 86-95.","DOI":"10.1109\/SFCS.1996.548467"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548300001140"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1017\/S096354830000184X"},{"key":"atypb29","first-page":"199","author":"Krivelevich M.","year":"2006","journal-title":"Berlin"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10076"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1137\/0136016"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/jdu063"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20727"},{"key":"atypb34","unstructured":"S. Plotkin, S. Rao, and W. Smith,\n                      Shallow excluded minors and improved graph decompositions\n                      , in Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'94), 1994, pp. 462-470."},{"key":"atypb35","first-page":"762","volume":"51","author":"Sarnak P.","year":"2004","journal-title":"Notices Amer. Math. Soc."},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-015-3013-2"},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2008.v004a005"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/17M1128721","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T12:54:14Z","timestamp":1787316854000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/17M1128721"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":36,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/17M1128721"],"URL":"https:\/\/doi.org\/10.1137\/17m1128721","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}