Packing Hamilton Cycles in Random and Pseudo-Random Hypergraphs

2011-02-16T00:00:00Z (GMT) by Alan Frieze Michael Krivelevich
<p>We say that a <em>k</em> -uniform hypergraph <em>C</em> is a Hamilton cycle of type <em>ℓ</em>, for some 1 ≤ <em>ℓ</em> ≤ <em>k</em>, if there exists a cyclic ordering of the vertices of <em>C</em>such that every edge consists of <em>k</em> consecutive vertices and for every pair of consecutive edges <em>E</em><sub><em>i</em>-1</sub>,<em>E</em><sub><em>i</em></sub> in <em>C</em> (in the natural ordering of the edges) we have |<em>E</em><sub><em>i</em>-1</sub> / <em>E</em><sub><em>i</em></sub>| = <em>ℓ</em>. We prove that for <em>k</em>/2 < <em>ℓ</em> ≤ <em>k</em>, with high probability almost all edges of the random <em>k</em> -uniform hypergraph<em>H</em>(<em>n</em>,<em>p</em>,<em>k</em>) with <em>p</em>(<em>n</em>) ≫ log <sup>2</sup><em>n</em>/<em>n</em> can be decomposed into edge-disjoint type <em>ℓ</em> Hamilton cycles. A slightly weaker result is given for <em>ℓ</em> = <em>k</em>/2. We also provide sufficient conditions for decomposing almost all edges of a pseudo-random <em>k</em> -uniform hypergraph into type <em>ℓ</em> Hamilton cycles, for <em>k</em>/2 ≤ <em>ℓ</em> ≤ <em>k</em>. For the case <em>ℓ</em> = <em>k</em> these results show that almost all edges of corresponding random and pseudo-random hypergraphs can be packed with disjoint perfect matchings. </p>