The minimum number of nonnegative edges in hypergraphs
- Series
- Graph Theory Seminar
- Time
- Wednesday, November 13, 2013 - 16:05 for 1 hour (actually 50 minutes)
- Location
- Skiles 005
- Speaker
- Hao Huang – Institute for Advanced Study and DIMACS
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.