{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T05:46:59Z","timestamp":1775800019008,"version":"3.50.1"},"reference-count":42,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T00:00:00Z","timestamp":1742860800000},"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,7]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    We show that every\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548325000070_inline1.png\"\/>\n                        <jats:tex-math>$(n,d,\\lambda )$<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    -graph contains a Hamilton cycle for sufficiently large\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548325000070_inline2.png\"\/>\n                        <jats:tex-math>$n$<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    , assuming that\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548325000070_inline3.png\"\/>\n                        <jats:tex-math>$d\\geq \\log ^{6}n$<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    and\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548325000070_inline4.png\"\/>\n                        <jats:tex-math>$\\lambda \\leq cd$<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    , where\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548325000070_inline5.png\"\/>\n                        <jats:tex-math>$c=\\frac {1}{70000}$<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    . This significantly improves a recent result of Glock, Correia, and Sudakov, who obtained a similar result for\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548325000070_inline6.png\"\/>\n                        <jats:tex-math>$d$<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    that grows polynomially with\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548325000070_inline7.png\"\/>\n                        <jats:tex-math>$n$<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    . The proof is based on a new result regarding the second largest eigenvalue of the adjacency matrix of a subgraph induced by a random subset of vertices, combined with a recent result on connecting designated pairs of vertices by vertex-disjoint paths in\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548325000070_inline8.png\"\/>\n                        <jats:tex-math>$(n,d,\\lambda )$<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    -graphs. We believe that the former result is of independent interest and will have further applications.\n                  <\/jats:p>","DOI":"10.1017\/s0963548325000070","type":"journal-article","created":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T04:30:10Z","timestamp":1742877010000},"page":"596-620","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":0,"title":["Hamiltonicity of sparse pseudorandom graphs"],"prefix":"10.1017","volume":"34","author":[{"given":"Asaf","family":"Ferber","sequence":"first","affiliation":[{"name":"University of California"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jie","family":"Han","sequence":"additional","affiliation":[{"name":"Beijing Institute of Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-8239-3633","authenticated-orcid":false,"given":"Dingjia","family":"Mao","sequence":"additional","affiliation":[{"name":"University of California"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Roman","family":"Vershynin","sequence":"additional","affiliation":[{"name":"University of California"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2025,3,25]]},"reference":[{"key":"S0963548325000070_ref36","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20235"},{"key":"S0963548325000070_ref18","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1963.10500830"},{"key":"S0963548325000070_ref30","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2019.04.002"},{"key":"S0963548325000070_ref32","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20827"},{"key":"S0963548325000070_ref41","doi-asserted-by":"publisher","DOI":"10.1016\/j.crma.2008.10.008"},{"key":"S0963548325000070_ref20","unstructured":"[20] Hyde, J. , Morrison, N. , M\u00fcyesser, A. and Pavez-Sign\u00e9, M. (2023) Spanning trees in pseudorandom graphs via sorting networks, arXiv preprint arXiv: 2311.03185."},{"key":"S0963548325000070_ref1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-54423-1_31"},{"key":"S0963548325000070_ref19","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-06-01126-8"},{"key":"S0963548325000070_ref15","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.21052"},{"key":"S0963548325000070_ref31","doi-asserted-by":"publisher","DOI":"10.1112\/blms.12237"},{"key":"S0963548325000070_ref13","volume-title":"Introduction to random graphs","author":"Frieze","year":"2016"},{"key":"S0963548325000070_ref6","volume-title":"Spectra of graphs","author":"Brouwer","year":"2011"},{"key":"S0963548325000070_ref39","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(72)90013-4"},{"key":"S0963548325000070_ref10","unstructured":"[10] Dragani\u0107, N. , Montgomery, R. , Correia, D. M. , Pokrovskiy, A. and Sudakov, B. (2024) Hamiltonicity of expanders: optimal bounds and applications, arXiv: 2402.06603."},{"key":"S0963548325000070_ref11","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579202"},{"key":"S0963548325000070_ref17","unstructured":"[17] Han, J. and Yang, D. (2022) Spanning trees in sparse expanders, arXiv preprint arXiv: 2211.04758."},{"key":"S0963548325000070_ref16","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22576"},{"key":"S0963548325000070_ref33","unstructured":"[33] Pavez-Sign\u00e9, M . (2023) Spanning trees in the square of pseudorandom graphs, arXiv: 2307.00322."},{"key":"S0963548325000070_ref40","doi-asserted-by":"publisher","DOI":"10.4064\/sm185-1-4"},{"key":"S0963548325000070_ref28","unstructured":"[28] K\u00fchn, D. and Osthus, D. (2014) Hamilton cycles in graphs and hypergraphs: an extremal perspective. In Proceedings of the International Congress of Mathematicians 2014, Seoul, Korea, vol. 4, KyungMoon Sa, Seoul, pp. 381\u2013406."},{"key":"S0963548325000070_ref26","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-32439-3_10"},{"key":"S0963548325000070_ref29","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20419"},{"key":"S0963548325000070_ref37","first-page":"307","volume-title":"North-Holland Mathematics Studies","author":"Thomason","year":"1987"},{"key":"S0963548325000070_ref12","unstructured":"[12] Frieze, A . (2019) Hamilton cycles in random graphs: a bibliography, arXiv preprint arXiv: 1901.07139."},{"key":"S0963548325000070_ref38","first-page":"1","article-title":"Random graphs, strongly regular graphs and Pseudorandom graphs","volume":"123","author":"Thomason","year":"1987","journal-title":"Surv. Comb."},{"key":"S0963548325000070_ref35","doi-asserted-by":"publisher","DOI":"10.1145\/1255443.1255449"},{"key":"S0963548325000070_ref5","first-page":"35","article-title":"The evolution of sparse graphs","author":"Bollob\u00e1s","year":"1984","journal-title":"Graph theory and combinatorics"},{"key":"S0963548325000070_ref25","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.10065"},{"key":"S0963548325000070_ref27","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2011.09.030"},{"key":"S0963548325000070_ref3","volume-title":"The probabilistic method","author":"Alon","year":"2016"},{"key":"S0963548325000070_ref4","doi-asserted-by":"publisher","DOI":"10.37236\/278"},{"key":"S0963548325000070_ref21","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"S0963548325000070_ref22","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2006.08.004"},{"key":"S0963548325000070_ref24","first-page":"529","volume-title":"Doklady Akademii Nauk","volume":"228","author":"Korshunov","year":"1976"},{"key":"S0963548325000070_ref42","volume-title":"West, etal, Introduction to graph theory","author":"West","year":"2001"},{"key":"S0963548325000070_ref23","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(83)90021-3"},{"key":"S0963548325000070_ref7","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2007.10129296"},{"key":"S0963548325000070_ref34","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(76)90068-6"},{"key":"S0963548325000070_ref2","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-007-2182-z"},{"key":"S0963548325000070_ref9","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s3-2.1.69"},{"key":"S0963548325000070_ref14","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2024.109984"},{"key":"S0963548325000070_ref8","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2013.12.004"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548325000070","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T04:49:24Z","timestamp":1775796564000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548325000070\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,3,25]]},"references-count":42,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,7]]}},"alternative-id":["S0963548325000070"],"URL":"https:\/\/doi.org\/10.1017\/s0963548325000070","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,3,25]]},"assertion":[{"value":"\u00a9 The Author(s), 2025. 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"}]}}