A linear bound on the Manickam-Miklos-Singhi Conjecture
arXiv:1308.2176
Abstract
Suppose that we have a set of numbers x_1, ..., x_n which have nonnegative sum. How many subsets of k numbers from {x_1, ..., x_n} must have nonnegative sum? Manickam, Miklos, and Singhi conjectured that for n at least 4k the answer is (n-1 \choose k-1). This conjecture is known to hold when n is large compared to k. The best known bounds are due to Alon, Huang, and Sudakov who proved the conjecture when n > 33k^2. In this paper we improve this bound by showing that there is a constant C such that the conjecture holds when n > Ck.
25 pages, 4 figures
Cited by in corpus (8)
- Minimal Number of Edges in Hypergraph Guaranteeing Perfect Fractional Matching and MMS Conjecture
- A New Quadratic Bound for the Manickam-Miklós-Singhi Conjecture
- A Note on the Manickam-Miklós-Singhi Conjecture for Vector Spaces
- The Manickam-Miklós-Singhi Conjectures for Sets and Vector Spaces
- General divisor function inequalities and the third cumulant
- Minimal number of edges in hypergraph guaranteeing perfect fractional matching and MMS conjecture, complete version
- The minimum number of nonnegative edges in hypergraphs
- The Maximum Number of Subset Divisors of a Given Size