Mathematics Events
[PAST EVENT] Mathematics Colloquium and EXTREEMS-QED Lecture: Ruth Luo (University of Illinois)
Access & Features
- Open to the public
Mathematics Colloquium and EXTREEMS-QED Lecture: Ruth Luo (University of Illinois at Urbana-Champaign)
Title: Uniform hypergraphs without long cycles are sparse
Abstract: The Erd\H{o}s?Gallai theorem gives an upper bound for the maximum number of edges in a graph with bounded circumference. We prove an analogue of this theorem for hypergraphs: for any k \geq 4 and n > r \geq k + 1, every n-vertex r-uniform hypergraph with no Berge cycle of length at least k has at most (k-1)(n-1)/r edges. Furthermore, this bound is sharp and we describe the extremal hypergraphs. The result also implies as a corollary the theorem of Gy\H{o}ri, Katona and Lemons that for n > r \geq k \geq 3, every n-vertex r-uniform hypergraph with no Berge path of length k has at most (k-1)n/(r+1) edges. This is a joint work with Alexandr Kostochka.
Contact
Gexin Yu