The minimum number of nonnegative edges in hypergraphs
type: Item
instance of: scholarly article
title: The minimum number of nonnegative edges in hypergraphs
zbMATH Open document ID: 1300.05142
author: Hao Huang
author: Benny Sudakov
published in: The Electronic Journal of Combinatorics
publication date: 2014-09-04T00:00:00Z
full work available at URL: https://arxiv.org/abs/1309.2549
full work available at URL: v21i3p7
review text: Summary: An \(r\)-uniform \(n\)-vertex hypergraph \(H\) is said to have the Manickam-Miklós-Singhi~(MMS) property if for every assignment of weights to its vertices with nonnegative sum, the number of edges whose total weight is nonnegative is at least the minimum degree of \(H\). In this paper we show that for \(n10r^3\), every \(r\)-uniform \(n\)-vertex hypergraph with equal codegrees has the MMS property, and the bound on \(n\) is essentially tight up to a constant factor. This result has two immediate corollaries. First it shows that every set of \(n10k^3\) real numbers with nonnegative sum has at least \(\binom{n-1}{k-1}\) nonnegative \(k\)-sums, verifying the Manickam-Miklós-Singhi conjecture for this range. More importantly, it implies the vector space Manickam-Miklós-Singhi conjecture which states that for \(n \geq 4k\) and any weighting on the \(1\)-dimensional subspaces of \(\mathbb{F}_{q}^n\) with nonnegative sum, the number of nonnegative \(k\)-dimensional subspaces is at least \({n-1 \brack k-1}_q\). We also discuss two additional generalizations, which can be regarded as analogues of the Erdős-Ko-Rado theorem on \(k\)-intersecting families.
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C65
Mathematics Subject Classification ID: 05D05
Mathematics Subject Classification ID: 05C22
zbMATH DE Number: 6340231
zbMATH Keywords: Erdős-Ko-Rado-type theorems
zbMATH Keywords: nonnegative edges
zbMATH Keywords: hypergraphs
MaRDI profile type: Publication
arXiv ID: 1309.2549
cites work: Nonnegative \(k\)-sums, fractional covers, and probability of small deviations
cites work: The Manickam-Miklós-Singhi conjectures for sets and vector spaces
cites work: INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
cites work: A linear programming approach to the Manickam-Miklós-Singhi conjecture
cites work: A note on the Manickam-Miklós-Singhi conjecture for vector spaces
cites work: Q3831020
cites work: Q3348035
cites work: First distribution invariants and EKR theorems
cites work: A method to count the positive 3-subsets in a set of real numbers with non-negative sum
cites work: A linear bound on the Manickam-Miklós-Singhi conjecture
cites work: An extension of the Erdoes, Ko, Rado theorem to t-designs
cites work: An improved bound for the Manickam-Miklós-Singhi conjecture
description: scientific article; zbMATH DE number 6340231