The Minimum Number of Non-negative Edges in Hypergraphs
| Speaker: | Hao Huang |
|---|---|
| Affiliation: | Institute for Advanced Study and DIMACS |
| Room: | Mathematics and Computer Building (MC) 5158 |
Abstract:
Extremal combinatorics studies the maximum or minimum possible size of a combinatorial structure satisfying certain properties. In this talk I will briefly review some recent developments in this field and connections with other areas, and 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 non-negative sum, the number of edges whose total weight is non-negative is at least the minimum degree of H. We show that all sufficiently large hypergraphs with equal codegrees have the MMS property. Our result resolves a long-standing conjecture by Manickam, Miklos, and Singhi, which states that for $n>4k$ and any weighting on the 1-dimensional subspaces of F_q^n with non-negative sum, the number of non-negative k-dimensional subspaces is at least n-1 k-1. Joint work with Benny Sudakov.