{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,2]],"date-time":"2022-04-02T23:48:16Z","timestamp":1648943296483},"reference-count":26,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2020,9,23]],"date-time":"2020-09-23T00:00:00Z","timestamp":1600819200000},"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":[[2021,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In an <jats:italic>r<\/jats:italic>-uniform hypergraph on <jats:italic>n<\/jats:italic> vertices, a tight Hamilton cycle consists of <jats:italic>n<\/jats:italic> edges such that there exists a cyclic ordering of the vertices where the edges correspond to consecutive segments of <jats:italic>r<\/jats:italic> vertices. We provide a first deterministic polynomial-time algorithm, which finds a.a.s. tight Hamilton cycles in random <jats:italic>r<\/jats:italic>-uniform hypergraphs with edge probability at least <jats:italic>C<\/jats:italic> log<jats:sup>3<\/jats:sup><jats:italic>n<\/jats:italic>\/<jats:italic>n<\/jats:italic>.<\/jats:p><jats:p>Our result partially answers a question of Dudek and Frieze, who proved that tight Hamilton cycles exist already for <jats:italic>p<\/jats:italic> = <jats:italic>\u03c9<\/jats:italic>(1\/<jats:italic>n<\/jats:italic>) for <jats:italic>r<\/jats:italic> = 3 and <jats:italic>p<\/jats:italic> = (<jats:italic>e<\/jats:italic> + <jats:italic>o<\/jats:italic>(1))\/<jats:italic>n<\/jats:italic> for <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548320000450_inline1.png\" \/><jats:tex-math>$r \\ge 4$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> using a second moment argument. Moreover our algorithm is superior to previous results of Allen, B\u00f6ttcher, Kohayakawa and Person, and Nenadov and \u0160kori\u0107, in various ways: the algorithm of Allen <jats:italic>et al.<\/jats:italic> is a randomized polynomial-time algorithm working for edge probabilities <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548320000450_inline2.png\" \/><jats:tex-math>$p \\ge {n^{ - 1 + \\varepsilon}}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, while the algorithm of Nenadov and \u0160kori\u0107 is a randomized quasipolynomial-time algorithm working for edge probabilities <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548320000450_inline3.png\" \/><jats:tex-math>$p \\ge C\\mathop {\\log }\\nolimits^8 n\/n$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>.<\/jats:p>","DOI":"10.1017\/s0963548320000450","type":"journal-article","created":{"date-parts":[[2020,9,23]],"date-time":"2020-09-23T08:04:17Z","timestamp":1600848257000},"page":"239-257","update-policy":"http:\/\/dx.doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":0,"title":["Finding tight Hamilton cycles in random hypergraphs faster"],"prefix":"10.1017","volume":"30","author":[{"given":"Peter","family":"Allen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christoph","family":"Koch","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Olaf","family":"Parczyk","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yury","family":"Person","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2020,9,23]]},"reference":[{"key":"S0963548320000450_ref9","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-99-00305-7"},{"key":"S0963548320000450_ref7","doi-asserted-by":"publisher","DOI":"10.37236\/535"},{"key":"S0963548320000450_ref16","first-page":"17","article-title":"Solution of a problem of P. Erd\u00f6s and A. R\u00e9nyi on Hamiltonian cycles in undirected graphs","volume":"31","author":"Korshunov","year":"1977","journal-title":"Metody Diskretn. Anal."},{"key":"S0963548320000450_ref19","unstructured":"[19] Montgomery, R. (2014) Embedding bounded degree spanning trees in random graphs. arXiv:1405.6559v2"},{"key":"S0963548320000450_ref8","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20404"},{"key":"S0963548320000450_ref15","first-page":"760","article-title":"Solution of a problem of Erd\u00f6s and R\u00e9nyi on Hamiltonian cycles in nonoriented graphs","volume":"17","author":"Korshunov","year":"1976","journal-title":"Sov. Math. Dokl."},{"key":"S0963548320000450_ref11","doi-asserted-by":"publisher","DOI":"10.1002\/9781118032718"},{"key":"S0963548320000450_ref13","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"S0963548320000450_ref12","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20224"},{"key":"S0963548320000450_ref22","unstructured":"[22] Poole, D. (2014) On weak Hamiltonicity of a random hypergraph. arXiv:1410.7446"},{"key":"S0963548320000450_ref21","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20782"},{"key":"S0963548320000450_ref26","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579348"},{"key":"S0963548320000450_ref2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(79)90045-X"},{"key":"S0963548320000450_ref6","doi-asserted-by":"publisher","DOI":"10.1016\/j.endm.2016.09.032"},{"key":"S0963548320000450_ref17","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548397003106"},{"key":"S0963548320000450_ref18","doi-asserted-by":"publisher","DOI":"10.1137\/120871729"},{"key":"S0963548320000450_ref4","unstructured":"[4] Bollob\u00e1s, B. (1984) The evolution of sparse graphs. In Graph Theory and Combinatorics (Cambridge, 1983), pp. 35\u201357. Academic Press."},{"key":"S0963548320000450_ref25","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548305007042"},{"key":"S0963548320000450_ref23","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(76)90068-6"},{"key":"S0963548320000450_ref10","doi-asserted-by":"publisher","DOI":"10.37236\/477"},{"key":"S0963548320000450_ref5","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579321"},{"key":"S0963548320000450_ref1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20519"},{"key":"S0963548320000450_ref20","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2019.106793"},{"key":"S0963548320000450_ref14","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(83)90021-3"},{"key":"S0963548320000450_ref24","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548399004150"},{"key":"S0963548320000450_ref3","doi-asserted-by":"publisher","DOI":"10.1137\/110839229"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548320000450","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,4]],"date-time":"2021-03-04T12:51:37Z","timestamp":1614862297000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548320000450\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,9,23]]},"references-count":26,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,3]]}},"alternative-id":["S0963548320000450"],"URL":"https:\/\/doi.org\/10.1017\/s0963548320000450","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,9,23]]},"assertion":[{"value":"\u00a9 The Author(s), 2020. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}}]}}