{
  "id": "1308.2176",
  "version": "v1",
  "published": "2013-08-09T16:48:25.000Z",
  "updated": "2013-08-09T16:48:25.000Z",
  "title": "A linear bound on the Manickam-Miklos-Singhi Conjecture",
  "authors": [
    "Alexey Pokrovskiy"
  ],
  "comment": "25 pages, 4 figures",
  "categories": [
    "math.CO",
    "math.NT"
  ],
  "abstract": "Suppose that we have a set of numbers x_1, ..., x_n which have nonnegative sum. How many subsets of k numbers from {x_1, ..., 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^2. In this paper we improve this bound by showing that there is a constant C such that the conjecture holds when n > Ck.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2013-08-09T16:48:25.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05D05"
    ],
    "keywords": [
      "manickam-miklos-singhi conjecture",
      "linear bound",
      "nonnegative sum",
      "conjecture holds"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 25,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2013arXiv1308.2176P"
    }
  }
}