Premium
Packing tight Hamilton cycles in 3‐uniform hypergraphs
Author(s) -
Frieze Alan,
Krivelevich Michael,
Loh PoShen
Publication year - 2012
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Book series
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
ISBN - 978-1-61197-251-1
DOI - 10.1002/rsa.20374
Subject(s) - hypergraph , combinatorics , modulo , mathematics , disjoint sets , enhanced data rates for gsm evolution , hamiltonian path , discrete mathematics , computer science , graph , telecommunications
Let H be a 3‐uniform hypergraph with n vertices. A tight Hamilton cycle C ⊂ 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 whp, 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. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011