TY - JOUR

T1 - The Manickam-Miklós-Singhi conjectures for sets and vector spaces

AU - Chowdhury, Ameera

AU - Sarkis, Ghassan

AU - Shahriari, Shahriar

PY - 2014/11

Y1 - 2014/11

N2 - 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 (n-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≥. 3. k, 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.

AB - 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 (n-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≥. 3. k, 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.

KW - Erdos-Ko-Rado type theorems

KW - Manickam-Miklós-Singhi conjecture

KW - Nonnegative sums

KW - Vector space analogues

UR - http://www.scopus.com/inward/record.url?scp=84905820990&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84905820990&partnerID=8YFLogxK

U2 - 10.1016/j.jcta.2014.07.004

DO - 10.1016/j.jcta.2014.07.004

M3 - Article

AN - SCOPUS:84905820990

SN - 0097-3165

VL - 128

SP - 84

EP - 103

JO - Journal of Combinatorial Theory. Series A

JF - Journal of Combinatorial Theory. Series A

IS - 1

ER -