A linear bound on the Manickam-Miklos-Singhi Conjecture

2013/08/09 by Alexey Pokrovskiy, Pokrovskiy, Alexey · 1 citation
Computer Science · Engineering · Mathematics · #05D05 #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #Number Theory (math.NT) #graph theory and CDMA systems

paper · doi:10.48550/arxiv.1308.2176

openalex publication_date 2013/08/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Suppose that we have a set of numbers x₁, ..., x_n which have nonnegative sum. How many subsets of k numbers from x₁, ..., x_n must have nonnegative sum? Manickam, Miklos, and Singhi conjectured that for n at least 4k the answer is (n-1 \choose k-1). This conjecture is known to hold when n is large compared to k. The best known bounds are due to Alon, Huang, and Sudakov who proved the conjecture when n > 33k². In this paper we improve this bound by showing that there is a constant C such that the conjecture holds when n > Ck.

Cited by

• A Note on the Manickam-Miklós-Singhi Conjecture for Vector Spaces

Related

• A New Quadratic Bound for the Manickam-Miklós-Singhi Conjecture
• A Branch-and-Cut Strategy for the Manickam-Miklos-Singhi Conjecture
• The Manickam-Miklós-Singhi Conjectures for Sets and Vector Spaces
• An improved bound for the Manickam-Miklós-Singhi conjecture
• The minimum number of nonnegative edges in hypergraphs