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.