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.