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

Abstract: More than twenty-five years ago, Manickam, Mikl'{o}s, and Singhi conjectured that for positive integers

n, k

with

n g e q 4 k

, every set of

n

real numbers with nonnegative sum has at least

k

-element subsets whose sum is also nonnegative. We verify this conjecture when

n g e q 8 k^{2}

, which simultaneously improves and simplifies a bound of Alon, Huang, and Sudakov and also a bound of Pokrovskiy when

k < 1 0^{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 s u b s e t V

to be the sum of the weights of all the

1

-dimensional subspaces it contains. We prove that if

n g e q 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.

Recommendations

Cites Work

Cited In (16)

This page was built for publication: The Manickam-Miklós-Singhi conjectures for sets and vector spaces