2013/09/10 by Hao Huang, Benny Sudakov, Huang, Hao +1
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #graph theory and CDMA systems #math.CO
paper · pdf · doi:10.48550/arxiv.1309.2549
openalex publication_date 2013/09/10 · arxiv created 2014/05/27 · arxiv updated 2014/05/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
An r-unform 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 n>10r3, 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>10k3 real numbers with nonnegative sum has at least \binomn-1k-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 >= 4k and any weighting on the 1-dimensional subspaces of Fqn with nonnegative sum, the number of nonnegative k-dimensional subspaces is at least n-1 \brack k-1q. We also discuss two additional generalizations, which can be regarded as analogues of the Erdős-Ko-Rado theorem on k-intersecting families.