Powers of Hamilton cycles in random graphs and tight Hamilton cycles in random hypergraphs

We show that for every \(k \in \mathbb{N}\) there exists \(C > 0\) such that if \(p^k \ge C \log^8 n / n\) then asymptotically almost surely the random graph \(G_{n,p}\) contains the \(k\)\textsuperscript{th} power of a Hamilton cycle. This determines the threshold for appearance of the square of...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2017-05
Main Authors: Nenadov, Rajko, Škorić, Nemanja
Format: Article
Language:English
Subjects:
Algorithms
Apexes
Graph theory
Polynomials
Randomization
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We show that for every \(k \in \mathbb{N}\) there exists \(C > 0\) such that if \(p^k \ge C \log^8 n / n\) then asymptotically almost surely the random graph \(G_{n,p}\) contains the \(k\)\textsuperscript{th} power of a Hamilton cycle. This determines the threshold for appearance of the square of a Hamilton cycle up to the logarithmic factor, improving a result of K\"uhn and Osthus. Moreover, our proof provides a randomized quasi-polynomial algorithm for finding such powers of cycles. Using similar ideas, we also give a randomized quasi-polynomial algorithm for finding a tight Hamilton cycle in the random \(k\)-uniform hypergraph \(G_{n,p}^{(k)}\) for \(p \ge C \log^8 n/ n\). The proofs are based on the absorbing method and follow the strategy of K\"uhn and Osthus, and Allen et al. The new ingredient is a general Connecting Lemma which allows us to connect tuples of vertices using arbitrary structures at a nearly optimal value of \(p\). Both the Connecting Lemma and its proof, which is based on Janson's inequality and a greedy embedding strategy, might be of independent interest.
ISSN:2331-8422