The Manickam-Miklós-Singhi Conjectures for Sets and Vector Spaces

Abstract

More than twenty-five years ago, Manickam, Miklós, and Singhi conjectured that for positive integers $n,k$ with $n\ge 4k$, every set of $n$ real numbers with nonnegative sum has at least $\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)$ $k$-element subsets whose sum is also nonnegative. We verify this conjecture when $n\ge 8k^2$, which simultaneously improves and simplifies a bound of Alon, Huang, and Sudakov and also a bound of Pokrovskiy when $k<10^{45}$. Moreover, our arguments resolve the vector space analogue of this conjecture. Let $V$ be an $n$-dimensional vector space over a finite field. Assign a real-valued weight to each $1$-dimensional subspace in $V$ so that the sum of all weights is zero. Define the weight of a subspace $S\subset V$ to be the sum of the weights of all the $1$-dimensional subspaces it contains. We prove that if $n\ge 3k$, then the number of $k$-dimensional subspaces in $V$ with nonnegative weight is at least the number of $k$-dimensional subspaces in $V$ that contain a fixed $1$-dimensional subspace. This result verifies a conjecture of Manickam and Singhi from 1988.

19 pages. To avoid repetition and because the calculations in the vector space case are less familiar, we only give here the argument for the vector space case when the proof of the corresponding statement for sets is essentially the same. Full details for the case of sets are available in the unpublished manuscript, arXiv:1403.1844. Version 6 has an updated bibliography

References in corpus (6)

• Minimal Number of Edges in Hypergraph Guaranteeing Perfect Fractional Matching and MMS Conjecture
• A linear bound on the Manickam-Miklos-Singhi Conjecture
• A Branch-and-Cut Strategy for the Manickam-Miklos-Singhi Conjecture
• Maximizing the number of nonnegative subsets
• A New Quadratic Bound for the Manickam-Miklós-Singhi Conjecture
• A Note on the Manickam-Miklós-Singhi Conjecture for Vector Spaces

Cited by in corpus (2)

• A Note on the Manickam-Miklós-Singhi Conjecture for Vector Spaces
• A New Quadratic Bound for the Manickam-Miklós-Singhi Conjecture