The Manickam-Miklós-Singhi Conjecture

Problem and Results Summary

Let ${\mathbf x} \in {\mathbb R}^n$ be a vector of $n$ real numbers with nonnegative sum: $\sum_{i=1}^n x_i \geq 0$. It is natural to ask how many partial sums must be nonnegative? Of course, all $2^n$ partial sums could be nonnegative when $x_i = 0$ always, so the interesting case is to try and minimize the number of nonnegative sums. One example is to take the vector

Such a vector has $2^{n-1}$ nonnegative partial sums and $\binom{n-1}{k-1}$ nonnegative partial $k$-sums. Bier and Manickam proved that this is the extremal example for partial sums of any order. The Manickam-Miklós-Singhi conjecture states that this is the extremal example for partial $k$-sums, given $n \geq 4k$.

Hartke and Stolee prove a stronger statement for all $k \leq 7$ and make a stronger conjecture.

Research Papers

S. G. Hartke, D. Stolee,
A Linear Programming Approach to the Manickam-Miklós-Singhi Conjecture,
*European Journal of Combinatorics*
36 (2014) 53-70.

Web Version ArXiv Version Official Version

Web Version ArXiv Version Official Version

Software

The *SearchLib* project MMSConjecture contains all source code related to our solution.
Full compilation requires TreeSearch, Utilities, and at least one of
GLPK or CPLEX.

See the *MMSConjecture* User Guide for more information on compilation and running the software.

Data

- Data values in Excel format
- Data values in CSV files:

Related Work

Computational Combinatorics Blog Post

Update to the Manickam-Miklós-Singhi Conjecture

Presentations

A linear programming approach to the Manickam-Miklós-Singhi Conjecture. *AMS Special Session on Partially Ordered Sets*, Louiville, KY.

Slides Paper

Slides Paper

A branch-and-bound strategy for the Manickam-Miklós-Singhi Conjecture. *AMS Special Session on Extremal Graph Theory*, Oxford, MS.

Slides Paper

Slides Paper