Computer Science/Discrete Mathematics Seminar II

A Dirac-Type Theorem for 3-Uniform Hypergraphs

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.

Date & Time

May 13, 2008 | 10:30am – 12:30pm

Location

West Bldg. Lecture Hall

Affiliation

Rutgers University and Member, School of Mathematics