Discrete Mathematics and Optimization Seminar

University of Illinois at Chicago
Monday March 5th at 4.30pm
Burnside 1205

Title. Quadruple systems with independent neighborhoods.

Abstract. What is the maximum number of edges in a k-uniform hypergraph on n vertices, provided that the neighborhood of each of its
(k-1)-sets of vertices is an independent set? When k=2 we are just asking for the maximum number of edges in a triangle-free graph on n vertices.
This was answered by Mantel in 1907 and is the first result of extremal graph theory. The case k=3 was answered in 2005 by Furedi,
Pikhurko and Simonovits. I will present a proof of the next case k=4. This is joint work with Zoltan Furedi and Oleg Pikhurko.