### Updates to the Manickam-Miklós-Singhi Conjecture

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.