A refinement of the Cameron-Erds conjecture

Noga Alon, József Balogh, Robert Morris, Wojciech Samotij

Research output: Contribution to journalArticle

10 Scopus citations

Abstract

In this paper, we study sum-free subsets of the set 1, ..., n}, that is, subsets of the first n positive integers which contain no solution to the equation x+y=z. Cameron and Erds conjectured in 1990 that the number of such sets is O(2n/2). This conjecture was confirmed by Green and, independently, by Sapozhenko. Here, we prove a refined version of their theorem, by showing that the number of sum-free subsets of [n] of size m is, for every 1 ≤ m ≤ ⌈n/2⌉. For, this result is sharp up to the constant implicit in the O(·). Our proof uses a general bound on the number of independent sets of size m in 3-uniform hypergraphs, proved recently by the authors, and new bounds on the number of integer partitions with small sumset.

Original languageEnglish (US)
Pages (from-to)44-72
Number of pages29
JournalProceedings of the London Mathematical Society
Volume108
Issue number1
DOIs
StatePublished - Jan 1 2014
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Mathematics(all)

Fingerprint Dive into the research topics of 'A refinement of the Cameron-Erds conjecture'. Together they form a unique fingerprint.

  • Cite this