Finding tight Hamilton cycles in random hypergraphs faster. (23rd March 2021)
- Record Type:
- Journal Article
- Title:
- Finding tight Hamilton cycles in random hypergraphs faster. (23rd March 2021)
- Main Title:
- Finding tight Hamilton cycles in random hypergraphs faster
- Authors:
- Allen, Peter
Koch, Christoph
Parczyk, Olaf
Person, Yury - Abstract:
- Abstract: In an r -uniform hypergraph on n vertices, a tight Hamilton cycle consists of n edges such that there exists a cyclic ordering of the vertices where the edges correspond to consecutive segments of r vertices. We provide a first deterministic polynomial-time algorithm, which finds a.a.s. tight Hamilton cycles in random r -uniform hypergraphs with edge probability at least C log 3 n / n . Our result partially answers a question of Dudek and Frieze, who proved that tight Hamilton cycles exist already for p = ω (1/ n ) for r = 3 and p = ( e + o (1))/ n for $r \ge 4$ using a second moment argument. Moreover our algorithm is superior to previous results of Allen, Böttcher, Kohayakawa and Person, and Nenadov and Škorić, in various ways: the algorithm of Allen et al. is a randomized polynomial-time algorithm working for edge probabilities $p \ge {n^{ - 1 + \varepsilon}}$, while the algorithm of Nenadov and Škorić is a randomized quasipolynomial-time algorithm working for edge probabilities $p \ge C\mathop {\log }\nolimits^8 n/n$ .
- Is Part Of:
- Combinatorics, probability and computing. Volume 30:Number 2(2021)
- Journal:
- Combinatorics, probability and computing
- Issue:
- Volume 30:Number 2(2021)
- Issue Display:
- Volume 30, Issue 2 (2021)
- Year:
- 2021
- Volume:
- 30
- Issue:
- 2
- Issue Sort Value:
- 2021-0030-0002-0000
- Page Start:
- 239
- Page End:
- 257
- Publication Date:
- 2021-03-23
- Subjects:
- 05C65, -- 05C80, -- 05C85
Combinatorial analysis -- Periodicals
Probabilities -- Periodicals
Computer science -- Mathematics -- Periodicals
511.6 - Journal URLs:
- http://journals.cambridge.org/action/displayJournal?jid=CPC ↗
- DOI:
- 10.1017/S0963548320000450 ↗
- Languages:
- English
- ISSNs:
- 0963-5483
- Deposit Type:
- Legaldeposit
- View Content:
- Available online (eLD content is only available in our Reading Rooms) ↗
- Physical Locations:
- British Library STI - ELD Digital Store
- Ingest File:
- 16600.xml