Abstract
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 Erd.os-Ko-Rado theorem.
Original language | English (US) |
---|---|
Pages (from-to) | 811-816 |
Number of pages | 6 |
Journal | SIAM Journal on Discrete Mathematics |
Volume | 28 |
Issue number | 2 |
DOIs | |
State | Published - 2014 |
Keywords
- Erdos-Ko-Rado
- Hall's theorem
- Nonnegative subsets