Discrete Mathematics and Optimization Seminar
DHRUV MUBAYI |
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.