An improved bound for the Manickam-Miklós-Singhi conjecture

Abstract

We show that for $n>k(4e\log k{)}^k$ every set $\{x_1,...,x_n\}$ of $n$ real numbers with ${\sum }_{i=0}^n{x}_i\ge 0$ has at least $\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)$ $k$-element subsets of a non-negative sum. This is a substantial improvement on the best previously known bound of $n>(k-1)(k^k+k^2)+k$, proved by Manickam and Miklós \cite{MM} in 1987.

Cited by in corpus (1)

• Nonnegative k-sums, fractional covers, and probability of small deviations