On the Conjectures of Nonnegative $k$-Sum and Hypergraph Matching

Computer Science/Discrete Mathematics Seminar II
Topic:On the Conjectures of Nonnegative $k$-Sum and Hypergraph Matching
Speaker:Hao Huang
Affiliation:University of California, Los Angeles; Member, School of Mathematics
Date:Tuesday, October 9
Time/Room:10:30am - 12:30pm/S-101
Video Link:https://video.ias.edu/csdm/huang

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.