2013/09/09 by Ameera Chowdhury, Chowdhury, Ameera, Ghassan Sarkis +3 · 1 citation
Computer Science · Mathematics · #05D05 #Advanced Graph Theory Research #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1309.2212
openalex publication_date 2013/09/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
More than twenty-five years ago, Manickam, Miklós, and Singhi conjectured that for positive integers n,k with n ≥ 4k, every set of n real numbers with nonnegative sum has at least \binomn-1k-1 k-element subsets whose sum is also nonnegative. We verify this conjecture when n ≥ 8k2, which simultaneously improves and simplifies a bound of Alon, Huang, and Sudakov and also a bound of Pokrovskiy when k < 1045. 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 ⊂ V to be the sum of the weights of all the 1-dimensional subspaces it contains. We prove that if n ≥ 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.