A New Quadratic Bound for the Manickam-Miklós-Singhi Conjecture

Abstract

More than twenty-five years ago, Manickam, Miklos, and Singhi conjectured that for positive integers $n,k$ with $n\ge 4k$, every set of $n$ real numbers with nonnegative sum has at least $\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)$ $k$-element subsets whose sum is also nonnegative. We verify this conjecture when $n\ge 8k^2$, which simultaneously improves and simplifies a bound of Alon, Huang, and Sudakov and also a bound of Pokrovskiy when $k<10^{45}$.

10 pages. The arguments here are similar to those in arXiv:1309.2212, where we tackle the Manickam-Miklos-Singhi conjectures for sets and vector spaces simultaneously. For the reader's convenience, we present the calculations for the case of sets in full detail in this unpublished manuscript. Version 4 has an updated bibliography

References in corpus (5)

• Minimal Number of Edges in Hypergraph Guaranteeing Perfect Fractional Matching and MMS Conjecture
• A linear bound on the Manickam-Miklos-Singhi Conjecture
• Maximizing the number of nonnegative subsets
• An improved bound for the Manickam-Miklós-Singhi conjecture
• The Manickam-Miklós-Singhi Conjectures for Sets and Vector Spaces

Cited by in corpus (1)

• The Manickam-Miklós-Singhi Conjectures for Sets and Vector Spaces