A Dirac-Type Theorem for 3-Uniform Hypergraphs

COMPUTER SCIENCE/DISCRETE MATH II
Topic:A Dirac-Type Theorem for 3-Uniform Hypergraphs
Speaker:Endre Szemeredi
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.