More than twenty years ago, Manickam, Miklos, and Singhi conjectured
that for any integers n, k satisfying n >= 4k, every set of n real
numbers with nonnegative sum has at least (n-1 choose k-1) subsets of k
elements whose sum is also nonnegative. In this talk we discuss the
connection of this problem with an old conjecture of Erdos on
hypergraph matchings, and with the question of estimating the
probability that the sum of nonnegative independent random variables
exceeds its expectation by a given amount. Using these connections
together with some probabilistic techniques, we verify the conjecture
for n >= ck^2. This substantially improves the best previously known
exponential lower bound n >= e^{k loglog k}.
This is joint work with Alon and Sudakov.
The ACO Seminar (2012-2013)