Nonnegative k-sums, fractional covers, and probability of small deviations

DOI10.1016/J.JCTB.2011.12.002MaRDI QIDQ414653zbMATHOpenAlexWikidataFDO

Authors Noga Alon, Hao Huang, Benny Sudakov

Publication date 11 May 2012

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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

zbMATH Keywords

hypergraph matchingfractional covernonnegative \(k\)-sum

Mathematics Subject Classification ID

Combinatorial aspects of finite geometries (05B25) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: More than twenty years ago, Manickam, Mikl'{o}s, and Singhi conjectured that for any integers $n,k$ satisfying $ngeq4k$, every set of $n$ real numbers with nonnegative sum has at least $$ $k$-element subsets whose sum is also nonnegative. In this paper we discuss the connection of this problem with matchings and fractional covers of hypergraphs, and with the question of estimating the probability that the sum of nonnegative independent random variables exceeds its expectation by a given amount. Using these connections together with some probabilistic techniques, we verify the conjecture for $ngeq33k^2$. This substantially improves the best previously known exponential lower bound $ngeq{e}^{ckloglogk}$. In addition we prove a tight stability result showing that for every $k$ and all sufficiently large $n$, every set of $n$ reals with a nonnegative sum that does not contain a member whose sum with any other $k-1$ members is nonnegative, contains at least $$ subsets of cardinality $k$ with nonnegative sum.

Recommendations

• An improved bound for the Manickam-Miklós-Singhi conjecture
• A linear bound on the Manickam-Miklós-Singhi conjecture
• A linear programming approach to the Manickam-Miklós-Singhi conjecture
• The Manickam-Miklós-Singhi conjectures for sets and vector spaces
• A remark on the problem of nonnegative \(k\)-subset sums

Cites work

• scientific article; zbMATH DE number 4198073 (Why is no real title available?)
• scientific article; zbMATH DE number 3685495 (Why is no real title available?)
• scientific article; zbMATH DE number 3478938 (Why is no real title available?)
• scientific article; zbMATH DE number 3221072 (Why is no real title available?)
• A method to count the positive 3-subsets in a set of real numbers with non-negative sum
• An improved bound for the Manickam-Miklós-Singhi conjecture
• Bounding probability of small deviation: a fourth moment approach
• Degrees giving independent edges in a hypergraph
• First distribution invariants and EKR theorems
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Large matchings in uniform hypergraphs and the conjectures of Erdős and samuels
• On Sums of Independent Random Variables with Unbounded Variance and Estimating the Average Degree in a Graph
• On a Chebyshev-Type Inequality for Sums of Independent Random Variables
• On a conjecture of Manickam and Singhi
• On perfect matchings in uniform hypergraphs with large minimum vertex degree
• SOME INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• The first distribution invariant of the Johnson-scheme

Cited in

(27)

• Divisor function inequalities, entropy, and the chance of being below average
• A linear programming approach to the Manickam-Miklós-Singhi conjecture
• A note on the Manickam-Miklós-Singhi conjecture
• Rainbow matchings for 3-uniform hypergraphs
• A note on the Manickam-Miklós-Singhi conjecture for vector spaces
• On the number of nonnegative sums for semi-partitions
• Miklós-Manickam-Singhi conjectures on partial geometries
• Solution of a problem on non-negative subset sums
• Rainbow perfect matchings for 4-uniform hypergraphs
• The minimum number of nonnegative edges in hypergraphs
• A better bound on the size of rainbow matchings
• The Erdős matching conjecture and concentration inequalities
• Improved bounds for Erdős' matching conjecture
• Large matchings in uniform hypergraphs and the conjectures of Erdős and samuels
• On the number of nonnegative sums for certain function
• Positive sum systems
• The adjacency matrix of a graph as a data table: a geometric perspective
• A linear bound on the Manickam-Miklós-Singhi conjecture
• Minimum number of edges in a hypergraph guaranteeing a perfect fractional matching and the MMS conjecture
• MMS-type problems for Johnson scheme
• Minimum supports of eigenfunctions of graphs: a survey
• The Manickam-Miklós-Singhi conjectures for sets and vector spaces
• On the number of nonnegative sums
• A remark on the problem of nonnegative \(k\)-subset sums
• On a Conjecture of Feige for Discrete Log-Concave Distributions
• Extremal problems for subset divisors
• On Rainbow Matchings for Hypergraphs

This page was built for publication: Nonnegative \(k\)-sums, fractional covers, and probability of small deviations

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