ACO The ACO Seminar (2012-2013)

Oct 25, 3:30pm, Wean 8220
Hao Huang, Institute for Advanced Study
On the conjectures of nonnegative k-sums and hypergraph matching


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.

Back to the ACO home page