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 , the function stores the minimum integer such that for all every vector with nonnegative total sum has at least nonnegative -sums. The conjecture states that .
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 .
N. Alon, H. Huang, and B. Sudakov. Nonnegative -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 .
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 , , and . 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 nonnegative -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 , , , and . Also, the extremal examples for small and are demonstrated and this provides a conjecture that 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 . 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 , although the constant term is . 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 .
Have a new update? Working on your own results? Send me an email so I can update this page.