Packing Hamilton Cycles in Random and Pseudo-Random Hypergraphs

Details Packing Hamilton Cycles in Random and Pseudo-Random Hypergraphs Packing Hamilton Cycles in Random and Pseudo-Random Hypergraphs

2010-03-09

arxiv.org/abs/1003.1958v1

Mathematics

Combinatorics

26 pages

Scientific paper

We say that a $k$-uniform hypergraph $C$ is a Hamilton cycle of type $\ell$, for some $1\le \ell \le 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|=\ell$. We prove that for $\ell \le k\le 2\ell$, with high probability almost all edges of a random $k$-uniform hypergraph $H(n,p,k)$ with $p(n)\gg \log^2 n/n$ can be decomposed into edge disjoint type $\ell$ Hamilton cycles. We also provide sufficient conditions for decomposing almost all edges of a pseudo-random $k$-uniform hypergraph into type $\ell$ Hamilton cycles, for $\ell \le k\le 2\ell$. For the case $\ell=k$ these results show that almost all edges of corresponding random and pseudo-random hypergraphs can be packed into disjoint perfect matchings.

Affiliated with

Also associated with

No associations

Rating

Packing Hamilton Cycles in Random and Pseudo-Random Hypergraphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Packing Hamilton Cycles in Random and Pseudo-Random Hypergraphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Packing Hamilton Cycles in Random and Pseudo-Random Hypergraphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-455798