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.
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 |
Archive Staff Only
 |
View Item |
