file.pdf (218.31 kB)
Download file

Optimal divisibility conditions for loose Hamilton cycles in random hypergraphs

Download (218.31 kB)
journal contribution
posted on 07.07.2012, 00:00 authored by Andrzej Dudek, Alan FriezeAlan Frieze, Po-Shen Loh, Shelley Speiss

In the random k-uniform hypergraph H(k)n,p of order n, each possible k-tuple appears independently with probability p. A loose Hamilton cycle is a cycle of order n in which every pair of consecutive edges intersects in a single vertex. It was shown by Frieze that if p≥c(logn)/n2 for some absolute constant c>0, then a.a.s. H(3)n,p contains a loose Hamilton cycle, provided that n is divisible by 4. Subsequently, Dudek and Frieze extended this result for any uniformity k≥4, proving that if p≫(logn)/nk−1, then H(k)n,p contains a loose Hamilton cycle, provided that n is divisible by 2(k−1). In this paper, we improve the divisibility requirement and show that in the above results it is enough to assume that n is a multiple of k−1, which is best possible.

History

Publisher Statement

Copyright the Authors

Date

07/07/2012

Usage metrics

Exports