The minimum number of nonnegative edges in hypergraphs

zbMATH Open1300.05142arXiv1309.2549MaRDI QIDQ405286FDOQ405286

Benny Sudakov, Hao Huang

Publication date: 4 September 2014

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: An r-unform n-vertex hypergraph H is said to have the Manickam-Mikl'os-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 n>10r^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 n>10k^3 real numbers with nonnegative sum has at least $$ nonnegative k-sums, verifying the Manickam-Mikl'os-Singhi conjecture for this range. More importantly, it implies the vector space Manickam-Mikl'os-Singhi conjecture which states that for n >= 4k and any weighting on the 1-dimensional subspaces of F_q^n with nonnegative sum, the number of nonnegative k-dimensional subspaces is at least $$. We also discuss two additional generalizations, which can be regarded as analogues of the ErdH{o}s-Ko-Rado theorem on k-intersecting families.

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

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• The Manickam-Miklós-Singhi conjectures for sets and vector spaces
• An improved bound for 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
• A linear bound on the Manickam-Miklós-Singhi conjecture

zbMATH Keywords

hypergraphs[https://portal.mardi4nfdi.de/w/index.php?title=+Special%3ASearch&search=Erd%EF%BF%BD%EF%BF%BDs-Ko-Rado-type+theorems&go=Go Erd��s-Ko-Rado-type theorems]nonnegative edges

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Signed and weighted graphs (05C22) Hypergraphs (05C65) Extremal set theory (05D05)

Cites Work

• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• A linear bound on the Manickam-Miklós-Singhi conjecture
• Title not available (Why is that?)
• The Manickam-Miklós-Singhi conjectures for sets and vector spaces
• First distribution invariants and EKR theorems
• Nonnegative \(k\)-sums, fractional covers, and probability of small deviations
• An extension of the Erdoes, Ko, Rado theorem to t-designs
• A method to count the positive 3-subsets in a set of real numbers with non-negative sum
• A linear programming approach to the Manickam-Miklós-Singhi conjecture
• Title not available (Why is that?)
• An improved bound for the Manickam-Miklós-Singhi conjecture
• A note on the Manickam-Miklós-Singhi conjecture for vector spaces

Cited In (7)

• A linear bound on the Manickam-Miklós-Singhi conjecture
• The Manickam-Miklós-Singhi conjectures for sets and vector spaces
• 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
• On the number of nonnegative sums for certain function
• Minimum supports of eigenfunctions of graphs: a survey

This page was built for publication: The minimum number of nonnegative edges in hypergraphs

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