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

DOI10.1016/J.JCTB.2011.12.002zbMATH Open1241.05100arXiv1104.1753OpenAlexW1973271905WikidataQ105583653 ScholiaQ105583653MaRDI QIDQ414653FDOQ414653

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)

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.

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

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

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)

Cites Work

• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Title not available (Why is that?)
• First distribution invariants and EKR theorems
• On perfect matchings in uniform hypergraphs with large minimum vertex degree
• Title not available (Why is that?)
• Title not available (Why is that?)
• SOME INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Bounding probability of small deviation: a fourth moment approach
• Title not available (Why is that?)
• 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
• A method to count the positive 3-subsets in a set of real numbers with non-negative sum
• Degrees giving independent edges in a hypergraph
• An improved bound for the Manickam-Miklós-Singhi conjecture
• On a conjecture of Manickam and Singhi
• On a Chebyshev-Type Inequality for Sums of Independent Random Variables
• The first distribution invariant of the Johnson-scheme

Cited In (28)

• Positive sum systems
• Extremal problems for subset divisors
• The minimum number of nonnegative edges in hypergraphs
• The adjacency matrix of a graph as a data table: a geometric perspective
• On the number of nonnegative sums
• 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
• Solution of a problem on non-negative subset sums
• A linear bound on the Manickam-Miklós-Singhi conjecture
• The Manickam-Miklós-Singhi conjectures for sets and vector spaces
• A linear programming approach to the Manickam-Miklós-Singhi conjecture
• A note on the Manickam-Miklós-Singhi conjecture
• A note on the Manickam-Miklós-Singhi conjecture for vector spaces
• On the number of nonnegative sums for semi-partitions
• A better bound on the size of rainbow matchings
• Rainbow perfect matchings for 4-uniform hypergraphs
• MMS-type problems for Johnson scheme
• On a Conjecture of Feige for Discrete Log-Concave Distributions
• Rainbow matchings for 3-uniform hypergraphs
• A robust Khintchine inequality, and algorithms for computing optimal constants in Fourier analysis and high-dimensional geometry
• Minimum number of edges in a hypergraph guaranteeing a perfect fractional matching and the MMS conjecture
• Miklós-Manickam-Singhi conjectures on partial geometries
• On the number of nonnegative sums for certain function
• A remark on the problem of nonnegative \(k\)-subset sums
• On Rainbow Matchings for Hypergraphs
• Divisor function inequalities, entropy, and the chance of being below average
• Minimum supports of eigenfunctions of graphs: a survey

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)