Name
Abstract | ||
|---|---|---|
Consider a 3-uniform hypergraph H with n vertices. A tight Hamilton cycle C ⊂ H is a collection of n edges for which there is an ordering of the vertices v1,..., vn where every triple of consecutive vertices {vi, vi+1, vi+2} is an edge of C (indices considered modulo n). We develop new techniques which show 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, 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.
|
Year | DOI | Venue |
|---|---|---|
2012 | 10.1002/rsa.20374 | SODA '11: 22nd ACM-SIAM Symposium on Discrete Algorithms
San Francisco
California
January, 2011 |
Keywords | Field | DocType |
edge-disjoint tight hamilton cycle,n vertex,wiley periodicals,3-uniform hypergraph h,tight hamilton cycle,vertices v1,hamilton cycle,n divisible,tight hamilton cycles whp,n edge,3-uniform hypergraphs,modulo n,distributed computing,leader election,randomized algorithms | Randomized algorithm,Discrete mathematics,Combinatorics,Vertex (geometry),Modulo,Hamiltonian path,Constraint graph,Hypergraph,Parity (mathematics),Mathematics | Journal |
Volume | Issue | ISSN |
40 | 3 | 1042-9832 |
ISBN | Citations | PageRank |
978-1-61197-251-1 | 11 | 0.95 |
References | Authors | |
18 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Alan M. Frieze | 1 | 4837 | 787.00 |
| michael krivelevich | 2 | 1688 | 179.90 |
| Po-Shen Loh | 3 | 133 | 18.68 |