Computer Science/Discrete Mathematics Seminar II

A twenty-year old conjecture by Manickam, Mikl\'os, and Singhi asked whether for any integers $n, k$ satisfying $n \ge 4k$, every set of $n$ real numbers with nonnegative sum always has at least $\binom{n-1}{k-1}$ $k$-element subsets whose sum is also nonnegative. In this talk we discuss the connection of this problem with an old question by Erd\H{o}s, who asks to determine the maximum possible number of edges in a $k$-uniform hypergraph on $n$ vertices with no matching of size $t$, 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 and probabilistic techniques, we verify the Manickam-Mikl\'os-Singhi conjecture for $n \ge 33k^2$. In the remaining time of the talk, we will give an overview of the progress on Erd\H os' conjecture, and discuss its application to a problem of existence of perfect matchings in uniform hypergraphs, and to a question about finding an optimal data allocation in a distributed storage system. This talk is based on joint works with Alon, Frankl, Loh, R\"odl, Ruci\'nski and Sudakov.