Abstract
For k∈Z+, let f (k) be the minimum integer N such that for all n ≥ N, every set of n real numbers with nonnegative sum has at least (n-1k-1)k-element subsets whose sum is also nonnegative. In 1988, Manickam, Miklós, and Singhi proved that f (k) exists and conjectured that f (k) ≤ 4. k. In this note, we prove f (3) = 11, f (4) ≤ 24, and f (5) ≤ 40, which improves previous upper bounds in these cases. Moreover, we show how our method could potentially yield a quadratic upper bound on f (k) We end by discussing how our methods apply to a vector space analogue of the Manickam-Miklós-Singhi conjecture.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 131-140 |
| Number of pages | 10 |
| Journal | European Journal of Combinatorics |
| Volume | 35 |
| DOIs | |
| State | Published - Jan 2014 |
Bibliographical note
Funding Information:The author learned of the Manickam–Miklós–Singhi conjecture at the CMA Reunion Conference I of IPAM’s “Combinatorics: Methods and Applications in Computer Science” program. She thanks Stephen Hartke and Derrick Stolee, who wrote computer programs that were used in the Appendix , and is grateful to the Summer 2012 Combinatorics REGS program at UIUC for facilitating fruitful discussions with them. She also thanks Chris Godsil, Igor Pak, Benny Sudakov and Jacques Verstraëte for their advice. Research supported by NSF grant DMS-1203982 .