Maximizing the number of nonnegative subsets

Noga Alon, Harout Aydinian, Hao Huang

Research output: Contribution to journalArticle

2 Scopus citations

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 languageEnglish (US)
Pages (from-to)811-816
Number of pages6
JournalSIAM Journal on Discrete Mathematics
Volume28
Issue number2
DOIs
StatePublished - 2014

Keywords

  • Erdos-Ko-Rado
  • Hall's theorem
  • Nonnegative subsets

Fingerprint Dive into the research topics of 'Maximizing the number of nonnegative subsets'. Together they form a unique fingerprint.

Cite this