Maximizing the Number of Nonnegative Subsets

DOI10.1137/130947295zbMATH Open1301.05346arXiv1312.0248OpenAlexW1981229012MaRDI QIDQ3192165FDOQ3192165

Hao Huang, Noga Alon, Harout Aydinian

Publication date: 26 September 2014

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: Given a set of $n$ real numbers, if the sum of 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 $$, 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 ErdH{o}s-Ko-Rado Theorem.

Full work available at URL: https://arxiv.org/abs/1312.0248

Recommendations

• Maximizing the number of independent sets of a fixed size
• On the maximum number of balancing subsets
• Solution of a problem on non-negative subset sums
• Extremal problems among subsets of a set
• scientific article; zbMATH DE number 3342001
• Max-Min Problems of Searching for Two Disjoint Subsets
• scientific article; zbMATH DE number 1786503
• On finding maximum-cardinality symmetric subsets
• Finding Subsets Maximizing Minimum Structures
• Publication:4886044

zbMATH Keywords

Hall's theoremErdős-Ko-Rado theoremnonnegative subsets

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Extremal set theory (05D05)

Cited In (4)

• On the Erdős-Ko-Rado theorem and the Bollobás theorem for \(t\)-intersecting families
• Extremal problems for subset divisors
• A generalization of Alon-Aydinian-Huang theorem
• Erd\H os-Ko-Rado type theorems for simplicial complexes via algebraic shifting

This page was built for publication: Maximizing the Number of Nonnegative Subsets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3192165)