MATH Seminar
| Title: Loose Hamilton cycles in Hypergraphs |
|---|
| Seminar: Combinatorics |
| Speaker: Mathias Schacht of Hamburg University |
| Contact: Dwight Duffus, dwight@mathcs.emory.edu |
| Date: 2010-12-03 at 4:00PM |
| Venue: W306 |
| Download Flyer |
| Abstract: A classic result of G. A. Dirac in graph theory asserts that every n-vertex graph $(n > 2)$ with minimum degree at least n/2 contains a spanning (so-called Hamilton) cycle. G. Y. Katona and H. A. Kierstead suggested a possible extension of this result for k-uniform hypergraphs. There a Hamilton cycle of an n-vertex hypergraph corresponds to an ordering of the vertices such that every k consecutive (modulo n) vertices in the ordering form an edge. Moreover, the minimum degree is the minimum $(k- 1)$-degree, i.e. the minimum number of edges containing a fixed set of k - 1 vertices. V. Rodl, A. Rucinski, and E. Szemeredi verified (approximately) the conjecture of Katona and Kierstead and showed that every n-vertex, k-uniform hypergraph with minimum $(k-1)$-degree $(1/2 + o(1))n$ contains such a tight Hamilton cycle. We study the similar question for Hamilton r-cycles.\\ \\ A Hamilton r-cycle in an n-vertex, k-uniform hypergraph $(1 < r < k)$ is an ordering of the vertices and an ordered subset of the edges such that each such edge corresponds to k consecutive (modulo n) vertices and two consecutive edges intersect in precisely r vertices. We prove sufficient (and approximately best possible) minimum $(k-1)$-degree conditions for Hamilton r-cycles if $r < k/2$ and minimum 1-degree conditions for Hamilton 1-cycles in 3-uniform hypergraphs. This is joint work with E. Buss and H. Han. |
See All Seminars