{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,25]],"date-time":"2026-06-25T20:24:31Z","timestamp":1782419071403,"version":"3.54.5"},"reference-count":32,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2024,11,19]],"date-time":"2024-11-19T00:00:00Z","timestamp":1731974400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2025,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We prove that any bounded degree regular graph with sufficiently strong spectral expansion contains an induced path of linear length. This is the first such result for expanders, strengthening an analogous result in the random setting by Dragani\u0107, Glock, and Krivelevich. More generally, we find long induced paths in sparse graphs that satisfy a mild upper-uniformity edge-distribution condition.<\/jats:p>","DOI":"10.1017\/s096354832400035x","type":"journal-article","created":{"date-parts":[[2024,11,19]],"date-time":"2024-11-19T08:47:53Z","timestamp":1732006073000},"page":"276-282","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":1,"title":["Long induced paths in expanders"],"prefix":"10.1017","volume":"34","author":[{"given":"Nemanja","family":"Dragani\u0107","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Peter","family":"Keevash","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"56","published-online":{"date-parts":[[2024,11,19]]},"reference":[{"key":"S096354832400035X_ref31","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(93)90230-Q"},{"key":"S096354832400035X_ref22","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548300001619"},{"key":"S096354832400035X_ref26","unstructured":"[26] Matula, D. W. (1976) The largest clique size in a random graph, Technical report, Dallas: Department of Computer Science, Southern Methodist University,"},{"key":"S096354832400035X_ref13","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548322000013"},{"key":"S096354832400035X_ref19","article-title":"Computers and intractability: A guide to the theory of NP-completeness, Freeman","volume":"174","author":"Garey","year":"1997","journal-title":"Fundamental"},{"key":"S096354832400035X_ref8","doi-asserted-by":"publisher","DOI":"10.1137\/20M1330609"},{"key":"S096354832400035X_ref7","first-page":"49","article-title":"Recent developments in graph Ramsey theory","volume":"424","author":"Conlon","year":"2015","journal-title":"Surveys in combinatorics"},{"key":"S096354832400035X_ref20","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(01)00222-8"},{"key":"S096354832400035X_ref9","doi-asserted-by":"publisher","DOI":"10.1007\/BF01788097"},{"key":"S096354832400035X_ref4","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100053056"},{"key":"S096354832400035X_ref17","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(90)90149-C"},{"key":"S096354832400035X_ref2","first-page":"20","article-title":"New lower bounds on the size-Ramsey number of a path","volume":"29","author":"Bal","year":"2022","journal-title":"Electron. J. Comb."},{"key":"S096354832400035X_ref21","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100051124"},{"key":"S096354832400035X_ref23","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-06-01126-8"},{"key":"S096354832400035X_ref3","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190070115"},{"key":"S096354832400035X_ref18","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(87)90039-6"},{"key":"S096354832400035X_ref28","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-27875-4"},{"key":"S096354832400035X_ref5","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-024-00103-5"},{"key":"S096354832400035X_ref30","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200911"},{"key":"S096354832400035X_ref25","first-page":"7","article-title":"Large trees in random graphs","volume":"28","author":"Ku\u010dera","year":"1987","journal-title":"Comment. Math. Uni. Carolinae"},{"key":"S096354832400035X_ref15","doi-asserted-by":"publisher","DOI":"10.1137\/16M1069717"},{"key":"S096354832400035X_ref11","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2023.12.003"},{"key":"S096354832400035X_ref24","doi-asserted-by":"publisher","DOI":"10.1109\/TEC.1958.5222529"},{"key":"S096354832400035X_ref16","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(83)90247-9"},{"key":"S096354832400035X_ref14","unstructured":"[14] Dragani\u0107, N. and Petrova, K. (2022) Size-Ramsey numbers of graphs with maximum degree three. arXiv preprint arXiv:2207.05048"},{"key":"S096354832400035X_ref29","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(92)90021-O"},{"key":"S096354832400035X_ref27","first-page":"93","article-title":"Combinatorial Gray codes\u2013an updated survey","volume":"DS26","author":"M\u00fctze","year":"2023","journal-title":"Electron. J. Comb."},{"key":"S096354832400035X_ref1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(88)90051-2"},{"key":"S096354832400035X_ref10","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199608\/09)9:1\/2<93::AID-RSA6>3.0.CO;2-6"},{"key":"S096354832400035X_ref32","first-page":"257","volume-title":"Annals of Discrete Math.","volume":"38","author":"\u0141uczak","year":"1988"},{"key":"S096354832400035X_ref12","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.21078"},{"key":"S096354832400035X_ref6","first-page":"127","volume-title":"Annals of discrete mathematics","volume":"55","author":"Chartrand","year":"1993"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S096354832400035X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,24]],"date-time":"2025-02-24T12:38:49Z","timestamp":1740400729000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S096354832400035X\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,11,19]]},"references-count":32,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,3]]}},"alternative-id":["S096354832400035X"],"URL":"https:\/\/doi.org\/10.1017\/s096354832400035x","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,11,19]]},"assertion":[{"value":"\u00a9 The Author(s), 2024. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (https:\/\/creativecommons.org\/licenses\/by\/4.0\/), which permits unrestricted re-use, distribution, and reproduction in any medium, provided the original work is properly cited.","name":"license","label":"License","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}