Updates to the Manickam-Miklós-Singhi Conjecture

by Derrick Stolee

It has been a busy year for the Manickam-Miklós-Singhi Conjecture. (See the earlier post on this topic for the important definitions.) Several new papers have appeared online or on the arXiv. Here is a brief discussion of these recent developments (organized by time of submission, as far as I can tell).

Recall that for k \geq 1, the function f(k) stores the minimum integer n_0 such that for all n \geq n_0 every vector (x_1,\dots,x_n) with nonnegative total sum has at least \binom{n-1}{k-1} nonnegative k-sums. The conjecture states that f(k) \leq 4k.

M. Tyomkyn, An improved bound for the Manickam-Miklós-Singhi Conjecture. European Journal of Combinatorics 33 (2012) 27-32.
Tyomkyn improves previous exponential bounds to find f(k) \leq k^2(4e\log k)^k.

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) (2012) 784-796.
Using the idea of fractional covers, the authors prove the first polynomial upper bound of f(k) \leq \min\{33k^2, 2k^3\}.

A. Chowdhury, A note on the Manickam-Miklós-Singhi Conjecture, European Journal of Combinatorics, Volume 35, January 2014, Pages 131–140.
Chowdhury extends her thesis work to provide new upper bounds of f(3) = 11, f(4) \leq 24, and f(5) \leq 40. The technique is a computer-assisted proof by using the computer to generate a certain type of cover on a hypergraph. This hypergraph contains sets that must be negative in order to avoid having at least \binom{n-1}{k-1} nonnegative k-sums. The way these sets are classified as such uses the shift poset and an interesting application of the Kruskal-Katona Theorem.

S. G. Hartke, D. Stolee, A linear programming approach to the Manickam-Miklós-Singhi Conjecture, to appear in European Journal of Combinatorics.
This is the work described in the previous post. Using a linear programming formulation and a very involved computer search, the authors verify that f(4) = 14, f(5) = 17, f(6) = 20, and f(7) = 23. Also, the extremal examples for small n and k are demonstrated and this provides a conjecture that f(k)/k limits to a value approximately 3.14157899.

P. Frankl, On the number of nonnegative sums, to appear in Journal of Combinatorial Theory, Series B.
Frankl produces a slightly weaker but much shorter proof than Alon, Huang, and Sudakov, showing f(k) \leq \frac{3}{2}k^3. Note this is a stronger result than Alon, Huang, and Sudakov’s cubic bound.

A. Pokrovskiy, A linear bound on the Manickam-Mikl ́ós-Singhi Conjecture, arXiv:1308.2176v1.
Pokrovskiy proves a linear bound of f(k) \leq Ck, although the constant term is C = 10^{46}. This is a very nice improvement, and I look forward to people lowering this constant through more careful analysis of his proof. However, Pokrovskiy points out that his proof as written will not achieve a value of C=4.

Have a new update? Working on your own results? Send me an email so I can update this page.