The minimum number of nonnegative edges in hypergraphs

MaRDI QIDQ405286zbMATHFDO

Authors Hao Huang, Benny Sudakov

Publication date 4 September 2014

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

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

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

zbMATH Keywords

hypergraphsnonnegative edgesErdős-Ko-Rado-type theorems

Mathematics Subject Classification ID

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

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.

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

Cites work

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

Cited in

(8)

• 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
• A linear bound on the Manickam-Miklós-Singhi 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

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)