Maximizing the Number of Nonnegative Subsets

DOI10.1137/130947295MaRDI QIDQ3192165zbMATH OpenOpenAlexFDO

Authors Noga Alon, Hao Huang, Harout Aydinian

Publication date 26 September 2014

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

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

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)

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.

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

Cited in

(8)

• On the Erdős-Ko-Rado theorem and the Bollobás theorem for \(t\)-intersecting families
• Extremal problems for subset divisors
• On the number of nonnegative sums
• Solution of a problem on non-negative subset sums
• On the number of nonnegative sums for semi-partitions
• A generalization of Alon-Aydinian-Huang theorem
• Erd\H os-Ko-Rado type theorems for simplicial complexes via algebraic shifting
• A remark on the problem of nonnegative \(k\)-subset sums

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)