Packing loose Hamilton cycles

Abstract: A subset

C

of edges in a

k

-uniform hypergraph

H

is a emph{loose Hamilton cycle} if

C

covers all the vertices of

H

and there exists a cyclic ordering of these vertices such that the edges in

C

are segments of that order and such that every two consecutive edges share exactly one vertex. The binomial random

k

-uniform hypergraph

H_{n, p}^{k}

has vertex set

[n]

and an edge set

E

obtained by adding each

k

-tuple

to

E

with probability

p

, independently at random. Here we consider the problem of finding edge-disjoint loose Hamilton cycles covering all but

o (| E |)

edges, referred to as the emph{packing problem}. While it is known that the threshold probability for the appearance of a loose Hamilton cycle in

H_{n, p}^{k}

is

p = T h e t a l e f t (f r a c l o g n n^{k - 1} i g h t)

, the best known bounds for the packing problem are around

p = e x t p o l y l o g (n) / n

. Here we make substantial progress and prove the following asymptotically (up to a polylog

(n)

factor) best possible result: For

p g e q l o g^{C} n / n^{k - 1}

, a random

k

-uniform hypergraph

H_{n, p}^{k}

with high probability contains

edge-disjoint loose Hamilton cycles. Our proof utilizes and modifies the idea of "online sprinkling" recently introduced by Vu and the first author.

Recommendations

Cites work

Cited in

(6)

This page was built for publication: Packing loose Hamilton cycles