ACO The ACO Seminar (2011-2012)

Jan 19, 3:30pm, Wean 8220
Deepak Bal, CMU
Packing Tight Hamilton Cycles in Uniform Hypergraphs


We say that a K-uniform hypergraph C is a Hamilton cycle of type L, for some 1 <= L <= 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| = L. We define a class of (epsilon,p)-regular hypergraphs, that includes random hypergraphs, for which we can prove the existence of a decomposition of almost all edges into type L Hamilton cycles, where L < K/2. 

This is joint work with Alan Frieze.

Back to the ACO home page