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 k-sums in a nonnegative sum of n real numbers. With this method, we proved a stronger statement than the conjecture for all k\leq 7 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.
MMS-Layers5

The Conjecture and Past Work

The Manickam-Miklós-Singhi Conjecture. If n \geq 4k, then every vector (x_1,\dots,x_n) \in {\mathbb R}^n with nonnegative sum contains at least \binom{n-1}{k-1} nonnegative k-sums.

Bier and Manickam were the first to prove that f(k) exists, but had the very exponential bound

     f(k) \leq k(k-1)^k(k-2)^k+k(k-1)^2(k-2)^2 + k^2

which was later improved incrementally by the following authors:

Manickam-Miklós, ’88 f(k) \leq (k-1)(k^k+k^2)+k
Bhattacharya, ’03 f(k) \leq 2^{k+1}e^kk^{k+1}
Tyomkyn, ’12 f(k) \leq k^2(4e\log k)^k
Alon, Huang, Sudakov, ’12 f(k) \leq \min\{33k^2,2k^3\}

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 f(k), less has been done to determine exact values of f(k).

f(1) = 1 Trivial
f(2) = 8 Exercise
f(3) \leq 12 Marino, Chiaselotti, ’02
f(3) = 11 Chowdhury, ’12
f(4) \leq 24 Chowdhury, ’12

We extend this direction by showing f(k) = 3k+2 for all k \in \{4,5,6,7\}. We shall crucially use the following lemma of Chowdhury:

Lemma (Chowdhury) If g(n,k) = \binom{n-1}{k-1}, then g(n+k,k) = \binom{n+k-1}{k-1}.

From this lemma, we “only” need to determine g(n,k) for a finite number of values n.

We now begin discussing our technique, which begins with a poset that arises after ordering our values as x_1 \geq x_2 \geq \cdots \geq x_n.

The Shift Poset

For the sake of our discussion, we will frequently identify a k-set S \subset [n] with the partial k-sum \sum_{i\in S} x_i. We define the shift poset on the k-subsets of [n] where S \succeq T for S = \{ i_1 < i_2 < \cdots < i_k\} and T = \{ j_1 < j_2 < \cdots < j_k\} when i_\ell \leq j_\ell for all \ell \in [k]. We say S is to the left of T when S \succeq T (and T is to the right of S). For example, see the following diagram of two such sets:

Figure 1. Two sets.

Figure 1. Two sets S \succeq T.

The reason for this ordering is that the partial sums have the ordering \sum_{i\in S} x_i \geq \sum_{j\in T}x_j whenever S \succeq T. 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 \{1,2,\dots,k\} is on the left corner, the right-most set \{ n-k+1,n-k+2,\dots,n\} 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.

Figure 2. The shift poset.

Figure 2. The shift poset.

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 k-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:

  • {\mathcal L}_k(S) is the set of all sets to the left of S. Let L_k(S) = |{\mathcal L}_k(S)|.
  • {\mathcal R}_k(S) is the set of all sets to the right of S. Let R_k(S) = |{\mathcal R}_k(S)|.
  • For two collections {\mathcal A}^+ and {\mathcal A}^- of k-sets, define {\mathcal L}_k({\mathcal A}^+) = \cup_{S \in {\mathcal A}^+} {\mathcal L}_k(S) and {\mathcal R}_k({\mathcal A}^-) = \cup_{S \in {\mathcal A}^-} {\mathcal R}_k(S).

Given a vector {\mathbf x} \in {\mathbb R}^n, the k-sets partition into those with nonnegative k-sum in {\mathbf x} and those with negative sum. This partition is split into a “left-closed” set and “right-closed” set. Have a picture:

Figure 3. The partition of nonnegative and negative sums for a vector x.

Figure 3. The partition of nonnegative and negative sums for a vector {\mathbf x} \in {\mathbb R}^n.

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 k-sums are guaranteed, even when the conjectured bound of \binom{n-1}{k-1} does not apply.

Definition. Let g(n,k) be the minimum number of nonnegative k-sums of a vector {\mathbf x} \in {\mathbb R}^n.

Our algorithm verifies that g(n,k) \geq t for some target value t by searching for a vector with strictly fewer than t nonnegative k-sums. If none is found, the inequality is true.

The Algorithm

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

Definition. Let {\mathcal P}(n,k,{\mathcal A}^+, {\mathcal A}^-) be the linear program defined as
    \min x_1
    subject to
    \sum_{i=1}^n x_i = 0
    x_i - x_{i+1} \geq 0 for all i \in \{1,\dots,n\}
    \sum_{i\in S}x_i \geq 0 for all S \in {\mathcal A}^+
    \sum_{i\in S}x_i \leq -1 for all S \in {\mathcal A}^-

The importance of this linear program is that there is a feasible point for {\mathcal P}(n,k,{\mathcal A}^+, {\mathcal A}^-) if and only if there is a vector {\mathbf x} \in {\mathbb R}^n with all sets in {\mathcal L}_k({\mathcal A}^+) having nonnegative sum and all sets in {\mathcal R}_k({\mathcal A}^-) having strictly negative sum.

Hence our algorithm proceeds as follows. At every search node, we have our collections {\mathcal A}^+ and {\mathcal A}^- of nonnegative and negative sets. We select a k-set S that is not yet decided to be nonnegative or negative, and we branch by placing S 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 t nonnegative k-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 |{\mathcal L}_k({\mathcal A}^+)| \geq t. Thus, if adding a set to {\mathcal A}^+ would make this inequality hold, we can immediately add it to {\mathcal A}^-. 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:

Figure #. Branching positively leads to new negative propagations.

Figure 5. Branching positively leads to new negative propagations.

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.

Figure #. Negative branching continues until the LP is infeasible.

Figure 6. Negative branching continues until the LP is infeasible.

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 k = 7.

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 f(k):

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

One thing we noticed from the sharp examples was that all of them had the form a^b\ (-b)^a, where by this we mean the vector has b copies of a followed by a copies of -b (and a+b =n). We tested these type of examples for k \leq 250 and discovered that the best examples for n > 3k were of the form 3^{n-3}\ (-(n-3))^3 until the sharp example (n-1)^1\ (-1)^{n-1} from the MMS conjecture became the best. This led to our new, stronger conjecture.

Conjecture (Hartke, Stolee, ’13). Let N_k be the least integer such that \binom{N_k-3}{k} \geq \binom{N_k-1}{k-1}. Then f(k) = N_k. Moreover, \lim_{k\to\infty} f(k)/k \approx 3.147899....

This conjecture would mean that the conjecture f(k) \leq 4k does not have the right constant out front. However, we cannot simply put the limit constant out front, since the value of N_k/k approaches it in the limit from both sides, as in the following plot:

Figure 7. The plot of N_k/k for k \leq 250.

Figure 7. A plot of N_k/k for 5\leq k \leq 250.

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 k-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).

Advertisements

Leave a Comment!

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

    f(4) = 14 f(5) = 17 f(6) = 20 f(7) = 23