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.