Packing Hamilton cycles in random and pseudo-random hypergraphs

Abstract: We say that a

k

-uniform hypergraph

C

is a Hamilton cycle of type

e l l

, for some

1 l e e l l l e k

, if there exists a cyclic ordering of the vertices of

C

such that every edge consists of

k

consecutive vertices and for every pair of consecutive edges

E_{i - 1}, E_{i}

in

C

(in the natural ordering of the edges) we have

| E_{i - 1} - E_{i} | = e l l

. We prove that for

e l l l e k l e 2 e l l

, with high probability almost all edges of a random

k

-uniform hypergraph

H (n, p, k)

with

p (n) g g l o g^{2} n / n

can be decomposed into edge disjoint type

e l l

Hamilton cycles. We also provide sufficient conditions for decomposing almost all edges of a pseudo-random

k

-uniform hypergraph into type

e l l

Hamilton cycles, for

e l l l e k l e 2 e l l

. For the case

e l l = k

these results show that almost all edges of corresponding random and pseudo-random hypergraphs can be packed into disjoint perfect matchings.

Recommendations

Cites Work

Cited In (27)

This page was built for publication: Packing Hamilton cycles in random and pseudo-random hypergraphs