Maximizing the Number of Nonnegative Subsets

Alon N, Aydinian H, Huang H. Maximizing the Number of Nonnegative Subsets. SIAM Journal on Discrete Mathematics. 2014;28(2):811-816.Given a set of n real numbers, if the sum of the elements of every subset of size larger than k is negative, what is the maximum number of subsets of nonnegative sum? In this note we show that the answer is (n-1 k-1) + (n-1 k-2) + ...+ (n-1 0) + 1, settling a problem of Tsukerman. We provide two proofs; the first establishes and applies a weighted version of Hall's theorem, and the second is based on an extension of the nonuniform Erdos-Ko-Rado theorem