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

Noga Alon, Hao Huang, Benny Sudakov

Abstract

The Manickam-Miklós-Singhi (MMS) conjecture posits that for $n \geq 4k$, any set of $n$ real numbers with a nonnegative sum contains at least $\binom{n-1}{k-1}$ subsets of size $k$ that also have a nonnegative sum. This paper establishes the first polynomial bound for this conjecture, proving it holds for $n \geq 33k^2$. By establishing a novel connection between extremal combinatorics and probabilistic tail bounds for sums of independent random variables, the authors also provide a tight stability result for large $n$.

Introduction

In the late 1980s, Manickam, Miklós, and Singhi introduced a problem that has since become a cornerstone of extremal combinatorics. The MMS conjecture asks: given a set $X$ of $n$ real numbers such that $\sum_{x \in X} x \geq 0$, what is the minimum number of $k$-element subsets whose sum is also nonnegative?

The conjectured lower bound is $\binom{n-1}{k-1}$. This value is motivated by a specific "star" construction: consider a set where one element is $n-1$ and the remaining $n-1$ elements are $-1$. The total sum is zero. Any $k$-element subset containing the large positive element will have a sum of $(n-1) - (k-1) = n-k$, which is nonnegative for $n \geq k$. There are exactly $\binom{n-1}{k-1}$ such subsets.

Despite its simple formulation, the conjecture has resisted proof for decades. While it was known to hold when $n$ is a multiple of $k$, general bounds for $n$ were previously exponential, such as $n \geq e^{ck \log \log k}$. This paper provides a significant leap forward by establishing the first polynomial bound.

Bridging Combinatorics and Probability

The authors' approach relies on translating the combinatorial problem into the language of hypergraph theory and then applying probabilistic analysis.

Hypergraph Modeling and Fractional Covers

The problem can be framed by considering the "bad" subsets—those $k$-element subsets with a negative sum. These are treated as edges in a $(k-1)$-uniform hypergraph. To prove the conjecture, one must show that the number of such edges cannot be too large.

A key innovation in this work is the use of fractional matching numbers ($\nu^*$) and fractional covering numbers ($\tau^*$). In a hypergraph, a matching is a set of disjoint edges. A fractional matching assigns a weight to each edge such that for every vertex, the sum of weights of edges containing it is at most 1. By looking at the fractional relaxation of the matching problem, the authors can utilize tools from linear programming and avoid the complexities associated with the Erdős Matching Conjecture.

Feige’s Inequality

The most critical technical bridge is the application of Feige’s Inequality. This probabilistic tool provides a bound on the probability that the sum of independent nonnegative random variables exceeds its expectation by a small amount. Specifically, if $X_1, \dots, X_n$ are independent nonnegative random variables with $E[\sum X_i] \leq 1$, Feige showed that $P(\sum X_i < 1) \geq 1/13$.

The authors demonstrate that the combinatorial problem of counting nonnegative $k$-sums is essentially equivalent to estimating these tail probabilities. By refining the constants associated with these deviations, they are able to bound the number of negative sums and thus prove the conjecture for $n \geq 33k^2$.

Stability and Structural Results

Beyond the main bound, the paper explores the "stability" of the MMS conjecture. They investigate whether the star construction is the only way to achieve a small number of nonnegative $k$-sums.

The authors prove a Hilton-Milner type result: if the set of numbers does not contain a "dominant" element (one that guarantees a nonnegative sum when paired with any other $k-1$ elements), the number of nonnegative $k$-sums increases significantly. For sufficiently large $n$, such a set must contain at least $\binom{n-1}{k-1} + \binom{n-k-1}{k-1} - 1$ nonnegative $k$-sums. This suggests that the star configuration is indeed the unique extremal case.

Conclusion

The transition from exponential to polynomial bounds ($O(k^2)$) represents a major milestone in the study of the MMS conjecture. While the ultimate goal of proving the conjecture for $n \geq 4k$ remains, the techniques introduced here—particularly the link between fractional hypergraph covers and probabilistic tail bounds—provide a robust framework for future improvements. Reducing the $33k^2$ bound to a linear $O(k)$ bound likely depends on further sharpening the constants in the underlying probabilistic inequalities.

Summary updated

Abstract

More than twenty years ago, Manickam, Miklós, and Singhi conjectured that for any integers $n, k$ satisfying $n \geq 4k$, every set of $n$ real numbers with nonnegative sum has at least $\binom{n-1}{k-1}$ $k$-element subsets whose sum is also nonnegative. In this paper we discuss the connection of this problem with matchings and fractional covers of hypergraphs, 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 together with some probabilistic techniques, we verify the conjecture for $n \geq 33k^2$. This substantially improves the best previously known exponential lower bound $n \geq e^{ck \log\log k}$. In addition we prove a tight stability result showing that for every $k$ and all sufficiently large $n$, every set of $n$ reals with a nonnegative sum that does not contain a member whose sum with any other $k-1$ members is nonnegative, contains at least $\binom{n-1}{k-1}+\binom{n-k-1}{k-1}-1$ subsets of cardinality $k$ with nonnegative sum.
BibTeX
@article{alon2012nonnegative,
  author = {Noga Alon and Hao Huang and Benny Sudakov},
  title = {{Nonnegative k-sums, fractional covers, and probability of small deviations}},
  journal = {J. Comb. Theory B},
  year = {2012},
  doi = {10.1016/j.jctb.2011.12.002},
}
Figure