Packing Hamilton cycles in random and pseudo-random hypergraphs

DOI10.1002/RSA.20396MaRDI QIDQ2909240zbMATH OpenOpenAlexWikidataFDO

Authors Michael Krivelevich, Alan Frieze

Publication date 30 August 2012

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1003.1958

zbMATH Keywords

packingHamilton cyclesrandom hypergraphspseudo-random

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Eulerian and Hamiltonian graphs (05C45) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: We say that a $k$-uniform hypergraph $C$ is a Hamilton cycle of type $ell$, for some $1leelllek$, 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 $elllekle2ell$, with high probability almost all edges of a random $k$-uniform hypergraph $H(n,p,k)$ with $p(n)gglo{g}^{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 $elllekle2ell$. 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.

Recommendations

• Packing tight Hamilton cycles in uniform hypergraphs
• Packing tight Hamilton cycles in 3-uniform hypergraphs
• Packing tight Hamilton cycles in 3-uniform hypergraphs
• Packing loose Hamilton cycles
• Counting and packing Hamilton \(\ell\)-cycles in dense hypergraphs

Cites work

• An approximate Dirac-type theorem for \(k\)-uniform hypergraphs
• Dirac-type results for loose Hamilton cycles in uniform hypergraphs
• Factors in random graphs
• Hamilton \(\ell \)-cycles in uniform hypergraphs
• Hamiltonian decompositions of complete \(k\)-uniform hypergraphs
• Loose Hamilton cycles in hypergraphs
• Loose Hamilton cycles in random 3-uniform hypergraphs
• Loose Hamilton cycles in random uniform hypergraphs
• On packing Hamilton cycles in \(\varepsilon\)-regular graphs
• Packing tight Hamilton cycles in 3-uniform hypergraphs
• Packing tight Hamilton cycles in uniform hypergraphs
• Probabilistic methods for algorithmic discrete mathematics
• Quasi-random graphs
• The Game of JumbleG
• Tight Hamilton cycles in random uniform hypergraphs

Cited in

(27)

• Packing tight Hamilton cycles in 3-uniform hypergraphs
• Decompositions of quasirandom hypergraphs into hypergraphs of bounded degree
• Packing tree factors in random and pseudo-random graphs
• Packing tight Hamilton cycles in uniform hypergraphs
• Packing loose Hamilton cycles
• Approximate Hamilton decompositions of random graphs
• On rainbow Hamilton cycles in random hypergraphs
• Weak and strong versions of the 1-2-3 conjecture for uniform hypergraphs
• A counting lemma for sparse pseudorandom hypergraphs
• Rainbow Hamilton cycles in random graphs
• Tight Hamilton cycles in random hypergraphs
• Factors and loose Hamilton cycles in sparse pseudo‐random hypergraphs
• Hamiltonicity and $\sigma$-hypergraphs
• Decomposing hypergraphs into cycle factors
• Pseudorandom hypergraph matchings
• Counting and packing Hamilton cycles in dense graphs and oriented graphs
• Decompositions of complete uniform hypergraphs into Hamilton Berge cycles
• Hamilton cycles in quasirandom hypergraphs
• Edge-disjoint Hamilton cycles in random graphs
• A note on non-isomorphic edge-color classes in random graphs
• Almost all Steiner triple systems are almost resolvable
• Packing tight Hamilton cycles in 3-uniform hypergraphs
• Euler tours in hypergraphs
• Packing, counting and covering Hamilton cycles in random directed graphs
• Counting and packing Hamilton \(\ell\)-cycles in dense hypergraphs
• On packing Hamilton cycles in \(\varepsilon\)-regular graphs
• Counting results for sparse pseudorandom hypergraphs. I.

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2909240)