{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,13]],"date-time":"2025-05-13T21:58:53Z","timestamp":1747173533848,"version":"3.40.5"},"reference-count":24,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2023,10,2]],"date-time":"2023-10-02T00:00:00Z","timestamp":1696204800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2024,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A set of vertices in a graph is a Hamiltonian subset if it induces a subgraph containing a Hamiltonian cycle. Kim, Liu, Sharifzadeh, and Staden proved that for large <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548323000317_inline1.png\"\/><jats:tex-math>\n$d$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, among all graphs with minimum degree <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548323000317_inline2.png\"\/><jats:tex-math>\n$d$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548323000317_inline3.png\"\/><jats:tex-math>\n$K_{d+1}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> minimises the number of Hamiltonian subsets. We prove a near optimal lower bound that takes also the order and the structure of a graph into account. For many natural graph classes, it provides a much better bound than the extremal one (<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548323000317_inline4.png\"\/><jats:tex-math>\n$\\approx 2^{d+1}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>). Among others, our bound implies that an <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548323000317_inline5.png\"\/><jats:tex-math>\n$n$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-vertex <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548323000317_inline6.png\"\/><jats:tex-math>\n$C_4$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-free graph with minimum degree <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548323000317_inline7.png\"\/><jats:tex-math>\n$d$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> contains at least <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548323000317_inline8.png\"\/><jats:tex-math>\n$n2^{d^{2-o(1)}}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> Hamiltonian subsets.<\/jats:p>","DOI":"10.1017\/s0963548323000317","type":"journal-article","created":{"date-parts":[[2023,10,2]],"date-time":"2023-10-02T09:17:41Z","timestamp":1696238261000},"page":"110-120","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":1,"title":["Many Hamiltonian subsets in large graphs with given density"],"prefix":"10.1017","volume":"33","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2385-1137","authenticated-orcid":false,"given":"Stijn","family":"Cambie","sequence":"first","affiliation":[]},{"given":"Jun","family":"Gao","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5735-7321","authenticated-orcid":false,"given":"Hong","family":"Liu","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2023,10,2]]},"reference":[{"key":"S0963548323000317_ref14","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20510"},{"key":"S0963548323000317_ref12","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"S0963548323000317_ref15","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548300001140"},{"key":"S0963548323000317_ref1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70766-0"},{"key":"S0963548323000317_ref6","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-020-4434-0"},{"key":"S0963548323000317_ref18","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2013.01.005"},{"key":"S0963548323000317_ref21","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2005.04.004"},{"key":"S0963548323000317_ref16","doi-asserted-by":"publisher","DOI":"10.1017\/S096354830000184X"},{"key":"S0963548323000317_ref17","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-017-3701-1"},{"key":"S0963548323000317_ref11","doi-asserted-by":"publisher","DOI":"10.5817\/CZ.MUNI.EUROCOMB23-084"},{"key":"S0963548323000317_ref10","doi-asserted-by":"publisher","DOI":"10.1093\/imrn\/rnab154"},{"key":"S0963548323000317_ref23","first-page":"1191","article-title":"A solution to Erd\u0151s and Hajnal\u2019s odd cycle problem","volume":"36","author":"Liu","year":"2023","journal-title":"J. Am. Math. Soc."},{"key":"S0963548323000317_ref22","doi-asserted-by":"publisher","DOI":"10.1112\/jlms.12019"},{"key":"S0963548323000317_ref3","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s3-2.1.69"},{"key":"S0963548323000317_ref19","unstructured":"[19] K\u00fchn, D. and Osthus, D. (2014) Hamilton cycles in graphs and hypergraphs: an extremal perspective. In Proceedings of the International Congress of Mathematicians\u2014Seoul 2014. Vol. IV, Kyung Moon Sa, Seoul, pp. 381\u2013406."},{"key":"S0963548323000317_ref4","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2023.03.002"},{"key":"S0963548323000317_ref8","doi-asserted-by":"publisher","DOI":"10.1137\/21M143488X"},{"key":"S0963548323000317_ref5","doi-asserted-by":"publisher","DOI":"10.1090\/bproc\/107"},{"key":"S0963548323000317_ref20","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2013.10.006"},{"key":"S0963548323000317_ref7","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2023.04.004"},{"key":"S0963548323000317_ref13","doi-asserted-by":"publisher","DOI":"10.1112\/plms.12059"},{"key":"S0963548323000317_ref2","doi-asserted-by":"publisher","DOI":"10.1090\/memo\/1154"},{"key":"S0963548323000317_ref24","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2022.07.008"},{"key":"S0963548323000317_ref9","doi-asserted-by":"publisher","DOI":"10.1017\/fms.2023.6"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548323000317","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,12,20]],"date-time":"2023-12-20T09:49:23Z","timestamp":1703065763000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548323000317\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,10,2]]},"references-count":24,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,1]]}},"alternative-id":["S0963548323000317"],"URL":"https:\/\/doi.org\/10.1017\/s0963548323000317","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"type":"print","value":"0963-5483"},{"type":"electronic","value":"1469-2163"}],"subject":[],"published":{"date-parts":[[2023,10,2]]},"assertion":[{"value":"\u00a9 The Author(s), 2023. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}}]}}