W&M Featured Events

Location

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

This Event Appears On

• W&M Featured Events
• Arts & Sciences Events
• Mathematics Events