Maximizing the Number of Nonnegative Subsets

Alon N, Aydinian H, Huang H (2014)
SIAM Journal on Discrete Mathematics 28(2): 811-816.

Zeitschriftenaufsatz | Veröffentlicht | Englisch
 
Download
Es wurde kein Volltext hochgeladen. Nur Publikationsnachweis!
Autor/in
; ;
Abstract / Bemerkung
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.
Stichworte
nonnegative subsets; Erdos-Ko-Rado; Hall's theorem
Erscheinungsjahr
2014
Zeitschriftentitel
SIAM Journal on Discrete Mathematics
Band
28
Ausgabe
2
Seite(n)
811-816
ISSN
0895-4801
Page URI
https://pub.uni-bielefeld.de/record/2690921

Zitieren

Alon N, Aydinian H, Huang H. Maximizing the Number of Nonnegative Subsets. SIAM Journal on Discrete Mathematics. 2014;28(2):811-816.
Alon, N., Aydinian, H., & Huang, H. (2014). Maximizing the Number of Nonnegative Subsets. SIAM Journal on Discrete Mathematics, 28(2), 811-816. doi:10.1137/130947295
Alon, N., Aydinian, H., and Huang, H. (2014). Maximizing the Number of Nonnegative Subsets. SIAM Journal on Discrete Mathematics 28, 811-816.
Alon, N., Aydinian, H., & Huang, H., 2014. Maximizing the Number of Nonnegative Subsets. SIAM Journal on Discrete Mathematics, 28(2), p 811-816.
N. Alon, H. Aydinian, and H. Huang, “Maximizing the Number of Nonnegative Subsets”, SIAM Journal on Discrete Mathematics, vol. 28, 2014, pp. 811-816.
Alon, N., Aydinian, H., Huang, H.: Maximizing the Number of Nonnegative Subsets. SIAM Journal on Discrete Mathematics. 28, 811-816 (2014).
Alon, Noga, Aydinian, Haratyun, and Huang, Hao. “Maximizing the Number of Nonnegative Subsets”. SIAM Journal on Discrete Mathematics 28.2 (2014): 811-816.