|COMPUTER SCIENCE/DISCRETE MATH II|
|Topic:||A Dirac-Type Theorem for 3-Uniform Hypergraphs|
|Affiliation:||Rutgers University and Member, School of Mathematics|
|Date:||Tuesday, May 13|
|Time/Room:||10:30am - 12:30pm/West Bldg. Lecture Hall|
A 3-uniform hypergraph is hamiltonian if for some cyclic ordering of its vertex set, every 3 consecutive vertices form an edge. In 1952 Dirac proved that if the minimum degree in an n-vertex graph is at least n/2 then the graph is hamiltonian. We prove an analogous result for uniform hypergraphs: For all n large enough, a sufficient condition for an n-vertex 3-uniform hypergraph to be hamiltonian is that each 2-element set of vertices is contained in at least n/2 edges. Joint work with Vojtech Rodl and Andrzej Rucinski.