{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,12]],"date-time":"2026-01-12T11:51:39Z","timestamp":1768218699581,"version":"3.49.0"},"reference-count":27,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2025,10,13]],"date-time":"2025-10-13T00:00:00Z","timestamp":1760313600000},"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":[[2026,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    A seminal result of Koml\u00f3s, S\u00e1rk\u00f6zy, and Szemer\u00e9di states that any\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548325100217_inline1.png\"\/>\n                        <jats:tex-math>$n$<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    -vertex graph\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548325100217_inline2.png\"\/>\n                        <jats:tex-math>$G$<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    with minimum degree at least\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548325100217_inline3.png\"\/>\n                        <jats:tex-math>$(1\/2+\\alpha )n$<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    contains 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=\"S0963548325100217_inline4.png\"\/>\n                        <jats:tex-math>$n$<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    -vertex tree\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548325100217_inline5.png\"\/>\n                        <jats:tex-math>$T$<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    of bounded degree. Recently, Pham, Sah, Sawhney, and Simkin extended this result to show that such graphs\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548325100217_inline6.png\"\/>\n                        <jats:tex-math>$G$<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    in fact support an\n                    <jats:italic>optimally spread distribution<\/jats:italic>\n                    on copies of a given\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548325100217_inline7.png\"\/>\n                        <jats:tex-math>$T$<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    , which implies, using the recent breakthroughs on the Kahn-Kalai conjecture, the\n                    <jats:italic>robustness<\/jats:italic>\n                    result 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=\"S0963548325100217_inline8.png\"\/>\n                        <jats:tex-math>$T$<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    is a subgraph of sparse random subgraphs of\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548325100217_inline9.png\"\/>\n                        <jats:tex-math>$G$<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    as well. Pham, Sah, Sawhney, and Simkin construct their optimally spread distribution by following closely the original proof of the Koml\u00f3s-S\u00e1rk\u00f6zy-Szemer\u00e9di theorem which uses the blow-up lemma and the Szemer\u00e9di regularity lemma. We give an alternative, regularity-free construction that instead uses the Koml\u00f3s-S\u00e1rk\u00f6zy-Szemer\u00e9di theorem (which has a regularity-free proof due to Kathapurkar and Montgomery) as a black box. Our proof is based on the simple and general insight that, if\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548325100217_inline10.png\"\/>\n                        <jats:tex-math>$G$<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    has linear minimum degree, almost all constant-sized subgraphs of\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548325100217_inline11.png\"\/>\n                        <jats:tex-math>$G$<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    inherit the same minimum degree condition 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=\"S0963548325100217_inline12.png\"\/>\n                        <jats:tex-math>$G$<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    has.\n                  <\/jats:p>","DOI":"10.1017\/s0963548325100217","type":"journal-article","created":{"date-parts":[[2025,10,13]],"date-time":"2025-10-13T08:47:30Z","timestamp":1760345250000},"page":"71-82","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":0,"title":["Random embeddings of bounded-degree trees with optimal spread"],"prefix":"10.1017","volume":"35","author":[{"given":"Paul","family":"Bastide","sequence":"first","affiliation":[{"name":"LaBRI"},{"name":"TU Delft"}]},{"given":"Cl\u00e9ment","family":"Legrand-Duchesne","sequence":"additional","affiliation":[{"name":"Jagiellonian University"}]},{"ORCID":"https:\/\/orcid.org\/0009-0006-3702-9749","authenticated-orcid":false,"given":"Alp","family":"M\u00fcyesser","sequence":"additional","affiliation":[{"name":"New College, University of Oxford"}]}],"member":"56","published-online":{"date-parts":[[2025,10,13]]},"reference":[{"key":"S0963548325100217_ref5","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-009-2360-2"},{"key":"S0963548325100217_ref21","doi-asserted-by":"publisher","DOI":"10.1090\/jams\/1028"},{"key":"S0963548325100217_ref22","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2023.11.002"},{"key":"S0963548325100217_ref23","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2024.04.003"},{"key":"S0963548325100217_ref25","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(02)00582-4"},{"key":"S0963548325100217_ref20","doi-asserted-by":"publisher","DOI":"10.19086\/aic.2022.3"},{"key":"S0963548325100217_ref1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.21209"},{"key":"S0963548325100217_ref26","doi-asserted-by":"publisher","DOI":"10.1017\/9781108332699.009"},{"key":"S0963548325100217_ref2","unstructured":"[2] Anastos, M. and Chakraborti, D. (2023) Robust Hamiltonicity in families of Dirac graphs. arXiv preprint arXiv:2309.12607."},{"key":"S0963548325100217_ref18","volume-title":"Algorithms and Combinatorics","volume":"23","author":"Molloy","year":"2002"},{"key":"S0963548325100217_ref24","unstructured":"[24] Pham, H. T. , Sah, A. , Sawhney, M. and Simkin, M. (2022) A toolkit for robust thresholds, arXiv:2210.03064."},{"key":"S0963548325100217_ref8","doi-asserted-by":"publisher","DOI":"10.1112\/blms.12896"},{"key":"S0963548325100217_ref11","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548307008474"},{"key":"S0963548325100217_ref9","unstructured":"[9] Joos, F. , Lang, R. and Sanhueza-Matamala, N. (2023) Robust Hamiltonicity. arXiv preprint arXiv:2312.15262."},{"key":"S0963548325100217_ref27","doi-asserted-by":"crossref","unstructured":"[27] Talagrand, M. (2010) Are many small sets explicitly small? Proceedings of the 42nd ACM Symposium on Theory of Computing, pp. 13\u201336.","DOI":"10.1145\/1806689.1806693"},{"key":"S0963548325100217_ref14","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2024.08.006"},{"key":"S0963548325100217_ref15","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548300001620"},{"key":"S0963548325100217_ref10","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2024.05.004"},{"key":"S0963548325100217_ref3","doi-asserted-by":"publisher","DOI":"10.1007\/s00208-008-0268-6"},{"key":"S0963548325100217_ref12","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-024-00116-0"},{"key":"S0963548325100217_ref6","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s3-2.1.69"},{"key":"S0963548325100217_ref13","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2022.04.007"},{"key":"S0963548325100217_ref4","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177729330"},{"key":"S0963548325100217_ref16","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548301004849"},{"key":"S0963548325100217_ref17","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-2014-05963-1"},{"key":"S0963548325100217_ref7","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2021.194.2.2"},{"key":"S0963548325100217_ref19","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2019.106793"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548325100217","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,1,12]],"date-time":"2026-01-12T08:49:21Z","timestamp":1768207761000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548325100217\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,13]]},"references-count":27,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,1]]}},"alternative-id":["S0963548325100217"],"URL":"https:\/\/doi.org\/10.1017\/s0963548325100217","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,10,13]]},"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, provided the original article 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"}]}}