UCL Discovery
UCL home » Library Services » Electronic resources » UCL Discovery

A linear bound on the Manickam-Miklos-Singhi conjecture

Pokrovskiy, A; (2015) A linear bound on the Manickam-Miklos-Singhi conjecture. Journal of Combinatorial Theory A , 133 pp. 280-306. 10.1016/j.jcta.2015.01.007. Green open access

[thumbnail of MMSLinearNov.pdf]
Preview
Text
MMSLinearNov.pdf - Accepted Version

Download (410kB) | Preview

Abstract

Suppose that we have a set S of n real numbers which have nonnegative sum. How few subsets of S of order k can have nonnegative sum? Manickam, Miklós, and Singhi conjectured that for the answer is . 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 . In this paper we improve this bound by showing that there is a constant C such that the conjecture holds when . This establishes the conjecture in a range which is a constant factor away from the conjectured bound.

Type: Article
Title: A linear bound on the Manickam-Miklos-Singhi conjecture
Open access status: An open access version is available from UCL Discovery
DOI: 10.1016/j.jcta.2015.01.007
Publisher version: https://doi.org/10.1016/j.jcta.2015.01.007
Language: English
Additional information: This version is the author accepted manuscript. For information on re-use, please refer to the publisher’s terms and conditions.
Keywords: Extremal combinatorics, Hypergraphs, Additive combinatorics, Katona's cycle method
UCL classification: UCL
UCL > Provost and Vice Provost Offices > UCL BEAMS
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences > Dept of Mathematics
URI: https://discovery.ucl.ac.uk/id/eprint/10112668
Downloads since deposit
44Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item