### A Branch-and-Cut Strategy for the Manickam-Miklós-Singhi Conjecture

#### by Derrick Stolee

Stephen Hartke and I recently uploaded our paper, A Branch-and-Cut Strategy for the Manickam-Miklós-Singhi Conjecture to the arXiv. We build a computational method to verify a conjecture involving the number of nonnegative -sums in a nonnegative sum of real numbers. With this method, we proved a stronger statement than the conjecture for all and formed a stronger conjecture.

The method makes use of linear programming techniques and software, so begins our discussion of linear and integer programming methods. Read on to discover the method and also to figure out what is going on with the picture below.

### The Conjecture and Past Work

**The Manickam-Miklós-Singhi Conjecture.** If , then every vector with nonnegative sum contains at least nonnegative -sums.

Bier and Manickam were the first to prove that exists, but had the *very* exponential bound

which was later improved incrementally by the following authors:

Manickam-Miklós, ’88 | |

Bhattacharya, ’03 | |

Tyomkyn, ’12 | |

Alon, Huang, Sudakov, ’12 |

In this final reference, the trio of Alon, Huang, and Sudakov proved a quadratic upper bound, vastly improving over the previous exponential bounds. While these papers focused on the asymptotic bounds on , less has been done to determine exact values of .

Trivial | |

Exercise | |

Marino, Chiaselotti, ’02 | |

Chowdhury, ’12 | |

Chowdhury, ’12 |

We extend this direction by showing for all . We shall crucially use the following lemma of Chowdhury:

**Lemma (Chowdhury)** If , then .

From this lemma, we “only” need to determine for a finite number of values .

We now begin discussing our technique, which begins with a poset that arises after ordering our values as .

### The Shift Poset

For the sake of our discussion, we will frequently identify a -set with the partial -sum . We define the *shift poset* on the -subsets of where for and when for all . We say is *to the left of* when (and is *to the right of* ). For example, see the following diagram of two such sets:

The reason for this ordering is that the partial sums have the ordering whenever . So, if we somehow “know” or “constrain” a sum to be nonnegative, all sums to the left are also nonnegative (and if a sum is strictly negative, all sums to the right are also negative).

We visualize the shift poset as a diamond, where the left-most set is on the left corner, the right-most set is on the right corner, and the largest antichain (which naturally sits somewhere halfway between these two extremes) stretches between the bottom and top corners, as below.

This poset has many nice properties, including being a lattice and also having the lexicographic and colexicographic orderings as linear extensions. Thus, our methods of iterating over all -sets using lex or colex play nice with the ordering. This is helpful for finding maximal or minimal sets under certain properties.

We use some notation to our advantage:

- is the set of all sets to the left of . Let .
- is the set of all sets to the right of . Let .
- For two collections and of -sets, define and .

Given a vector , the -sets partition into those with nonnegative -sum in and those with negative sum. This partition is split into a “left-closed” set and “right-closed” set. Have a picture:

Our goal, then, is to search for the partition first, and then the vector satisfying that partition. If there are fewer nonnegative sets than our target, then the vector will be a counterexample. Otherwise, when we fail to find a suitable partition (and vector), we have guaranteed that no counterexample exists. What is even better is that we can find exactly how many nonnegative -sums are guaranteed, even when the conjectured bound of does not apply.

**Definition.** Let be the minimum number of nonnegative -sums of a vector .

Our algorithm verifies that for some target value by searching for a vector with strictly fewer than nonnegative -sums. If none is found, the inequality is true.

### The Algorithm

A simple algorithm would be to brute-force test all partitions of -sets into two parts that are left- and right-closed, respectively. Moreover, we only need to test those with fewer than sets in the nonnegative part. However, we need to connect this finite, discrete problem with the continuous problem of vectors in . For this, we use linear programming.

**Definition.** Let be the linear program defined as

subject to

for all

for all

for all

The importance of this linear program is that there is a feasible point for if and only if there is a vector with all sets in having nonnegative sum and all sets in having strictly negative sum.

Hence our algorithm proceeds as follows. At every search node, we have our collections and of nonnegative and negative sets. We select a -set that is not yet decided to be nonnegative or negative, and we branch by placing in one of these collections. This adds a constraint to the linear program (hence the “branch-and-cut” strategy) and we can test for feasibility. If the linear program is infeasible, we can prune the search tree. Otherwise, we test our optimal vector for having fewer than nonnegative -sums. If it is not a counterexample, we select again and branch.

One thing we can do very quickly is determine that no counterexample will be found when . Thus, if adding a set to would make this inequality hold, we can immediately add it to . We have a few methods for making this decision, and testing them efficiently was a nontrivial exercise.

Now, when we branch to make a set have nonnegative sum, this increases the number of sets we can guarantee to be strictly negative. These branches collapse the poset into a very small window of sets, and we quickly find the linear program infeasible. Click on the figure below for a larger view of this process:

However, we don’t get the advantage of this propagation when we branch to make a set negative. Instead, we continue adding negative sets until the linear program becomes infeasible (due to too many strictly negative sums while having a nonnegative total sum). This is still a finite amount of time, but it leads to a very unbalanced search tree, which is not ideal for parallelization.

To improve this issue of the unbalanced algorithm, we added the following propagation step: If branching a set to have negative sum makes the linear program infeasible, then make the set have nonnegative sum. This test can be run on all sets before any branching is done. However, this test is very time-consuming. For small cases, it leads to no branching at all, but quickly becomes intractable to test that many linear programs. So, we randomly sample sets that are not in either side of the partition and make this test. We continue sampling until either we make some number of samples and the test does not make a change or a time limit runs out. This last random step is a zero-error randomized algorithm (so it always gives the right answer, but the run time is a random variable) and allows us to stretch our computation to verify the conjecture for .

### Results and New Conjecture

By implementing and executing our algorithm, we verify a stronger statement than the MMS conjecture and use that data to formulate a stronger conjecture. Here are the values of :

Thus, for , $latex $f(k) = 3k+2$. This does not always hold. For instance, we know that . See the paper for all the data for the values of and the sharp examples.

One thing we noticed from the sharp examples was that all of them had the form , where by this we mean the vector has copies of followed by copies of (and ). We tested these type of examples for and discovered that the best examples for were of the form until the sharp example from the MMS conjecture became the best. This led to our new, stronger conjecture.

**Conjecture (Hartke, Stolee, ’13).** Let be the least integer such that . Then . Moreover, .

This conjecture would mean that the conjecture does not have the right constant out front. However, we cannot simply put the limit constant out front, since the value of approaches it in the limit from both sides, as in the following plot:

### Conclusions

This computational method gave us four new cases of a conjecture that has stood the test of time. Moreover, we found much more data on the conjecture than was previously known and used this data to formulate a stronger conjecture. Hopefully someone will use this information to find an insight that leads to a full proof of at least the MMS Conjecture (but maybe the HS Conjecture will last a bit longer?).

### References

S. G. Hartke, D. Stolee, A Branch-and-Cut Strategy for the Manickam-Miklós-Singhi Conjecture, arXiv:1302. [math.CO].

N. Alon, H. Huang, and B. Sudakov. Nonnegative -sums, fractional covers, and probability of small deviations. *Journal of Combinatorial Theory, Series B* **103**(3), 784-796 (2012).

A. Bhattacharya, On a conjecture of Manickam and Singhi. *Discrete Mathematics* **272**, 259-261 (2003).

T. Bier, N. Manickam, The first distribution invariant of the Johnson-scheme. *Southeast Asian Bulletin of Mathematics* **11**(1), 61-68 (1987).

G. Chiaselotti, On a problem concerning the weight functions. *European Journal of Combinatorics* **23**, 15-22 (2002).

G. Chiaselotti, G. Infante, G. Marino, New results related to a conjecture of Manickam and Singhi. *European Journal of Combinatorics* **29**, 361-368 (2008).

A. N. Chowdhury, *Shadows and Intersections*. Ph.D. dissertation, University of California San Diego (2012).

N. Manickam and D. Miklós. On the number of nonnegative partial sums of a nonnegative sum. In *Combinatorics* (Eger, 1987), volume 52 of *Colloq. Math. Soc. János Bolyai*, pages 385-392. North-Holland, Amsterdam, (1988).

N. Manickam and N. M. Singhi. First distribution invariants and EKR theorems. *Journal of Combinatorial Theory, Series A* **48**(1), 91-103, (1988).

G. Marino, G. Chiaselotti, A Method to Count the Positive 3-Subsets in a Set of Real Numbers with Nonnegative Sum. *European Journal of Combinatorics* **23**, 619-629 (2002).

M. Tyomkyn, An improved bound for the Manickam-Miklós-Singhi Conjecture. *European Journal of Combinatorics* **33**, 27-32 (2012).