The minimum number of nonnegative edges in hypergraphs

Combinatorics Seminar
Event time: 
Friday, March 28, 2014 - 10:00am to 11:00am
215 LOM
Hao Huang
Speaker affiliation: 
Event description: 

Extremal combinatorics studies the maximum or minimum possible size of a combinatorial structure satisfying certain properties. In this talk I will review some results and recent developments in this field and their connections with other areas, and then focus on the following extremal problem. A hypergraph H is said to have the MMS property if for every assignment of weights to its vertices with nonnegative sum, the number of edges whose total weight is nonnegative is at least the minimum degree of H. We show that all sufficiently large hypergraphs with equal codegrees have the MMS property, and prove a long-standing conjecture by Manickam, Miklos, and Singhi as a corollary.