Title: The Minimum Number of Nonnegative Edges in Hypergraphs
Speaker: Hao Huang, IAS and DIMACS
Date: Tuesday, October 15, 2013 2:00pm
Location: Hill Center, Room 525, Rutgers University, Busch Campus, Piscataway, NJ
An r-unform n-vertex hypergraph H is said to have the Manickam-Miklos-Singhi (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. In this talk I will show that for n>10r^3, every r-uniform n-vertex hypergraph with equal codegrees has the MMS property, and the bound on n is essentially tight up to a constant factor. An immediate corollary of this result is the vector space Manickam-Miklos-Singhi conjecture which states that for n>=4k and any weighting on the 1-dimensional subspaces of F_q^n with nonnegative sum, the number of nonnegative k-dimensional subspaces is at least ${n-1 brack k-1}_q$. I will also discuss two additional generalizations, which can be regarded as analogues of the Erdos-Ko-Rado theorem on k-intersecting families. This is joint work with Benny Sudakov.
See: http://math.rutgers.edu/seminars/allseminars.php?sem_name=Discrete%20Math