Packing tight Hamilton cycles in 3-uniform hypergraphs

DOI10.1002/RSA.20374zbMATH Open1238.05184DBLPjournals/rsa/FriezeKL12arXiv1005.4711OpenAlexW2046583195WikidataQ57401444 ScholiaQ57401444MaRDI QIDQ2884005FDOQ2884005

Michael Krivelevich, Alan Frieze, Po-Shen Loh

Publication date: 14 May 2012

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

Abstract: Let H be a 3-uniform hypergraph with N vertices. A tight Hamilton cycle C subset H is a collection of N edges for which there is an ordering of the vertices v_1, ..., v_N such that every triple of consecutive vertices {v_i, v_{i+1}, v_{i+2}} is an edge of C (indices are considered modulo N). We develop new techniques which enable us to prove that under certain natural pseudo-random conditions, almost all edges of H can be covered by edge-disjoint tight Hamilton cycles, for N divisible by 4. Consequently, we derive the corollary that random 3-uniform hypergraphs can be almost completely packed with tight Hamilton cycles w.h.p., for N divisible by 4 and P not too small. Along the way, we develop a similar result for packing Hamilton cycles in pseudo-random digraphs with even numbers of vertices.

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

Recommendations

• Packing tight Hamilton cycles in 3-uniform hypergraphs
• Packing tight Hamilton cycles in uniform hypergraphs
• Packing Hamilton cycles in random and pseudo-random hypergraphs
• Tight Hamilton cycles in random hypergraphs
• Tight Hamilton cycles in random uniform hypergraphs

zbMATH Keywords

packingrandom hypergraphstight Hamilton cycles

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Eulerian and Hamiltonian graphs (05C45) Paths and cycles (05C38) Hypergraphs (05C65)

Cites Work

• Sparse pseudo‐random graphs are Hamiltonian
• Probabilistic methods for algorithmic discrete mathematics
• Some Theorems on Abstract Graphs
• Quasi-random graphs
• Dirac-type results for loose Hamilton cycles in uniform hypergraphs
• Hamilton \(\ell \)-cycles in uniform hypergraphs
• Packing Hamilton cycles in random and pseudo-random hypergraphs
• Loose Hamilton cycles in hypergraphs
• Loose Hamilton cycles in random 3-uniform hypergraphs
• On packing Hamilton cycles in \(\varepsilon\)-regular graphs
• Edge-disjoint Hamilton cycles in graphs
• Hamilton decompositions of complete 3-uniform hypergraphs
• Hamilton decompositions of regular tournaments
• Title not available (Why is that?)
• On two Hamilton cycle problems in random graphs
• Random matchings which induce Hamilton cycles and Hamiltonian decompositions of random regular graphs
• Title not available (Why is that?)

Cited In (17)

• Recent advances on the Hamiltonian problem: survey III
• Decompositions of quasirandom hypergraphs into hypergraphs of bounded degree
• Packing tree factors in random and pseudo-random graphs
• Rainbow hamilton cycles in random graphs
• Approximate Hamilton decompositions of random graphs
• Tight Hamilton cycles in random hypergraphs
• A counting lemma for sparse pseudorandom hypergraphs
• Factors and loose Hamilton cycles in sparse pseudo‐random hypergraphs
• Edge-disjoint Hamilton cycles in random graphs
• Decompositions of complete uniform hypergraphs into Hamilton Berge cycles
• Hamilton cycles in quasirandom hypergraphs
• Euler tours in hypergraphs
• Minimum vertex degree condition for tight Hamiltonian cycles in 3‐uniform hypergraphs
• On packing Hamilton cycles in \(\varepsilon\)-regular graphs
• Covering 3‐uniform hypergraphs by vertex‐disjoint tight paths
• Counting results for sparse pseudorandom hypergraphs. I.
• Regular uniform hypergraphs, \(s\)-cycles, \(s\)-paths and their largest Laplacian H-eigenvalues

This page was built for publication: Packing tight Hamilton cycles in 3-uniform hypergraphs

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