Derrick Stolee - Iowa State University - Research Browser

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

$x_1 = n-1,\quad x_2 = -1,\quad \dots,\quad x_n = -1$.

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
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
Related Work
Presentations
A linear programming approach to the Manickam-Miklós-Singhi Conjecture. AMS Special Session on Partially Ordered Sets, Louiville, KY.
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

Derrick Stolee - Iowa State University - Research Browser