TY - JOUR

T1 - A refinement of the Cameron-Erds conjecture

AU - Alon, Noga

AU - Balogh, József

AU - Morris, Robert

AU - Samotij, Wojciech

N1 - Funding Information:
Research supported in part by an ERC advanced grant, an USA-Israeli BSF grant and the Israeli I-Core program (Noga Alon); an NSF CAREER Grant DMS-0745185, UIUC Campus Research Board Grant 11067 and OTKA Grant K76099 (József Balogh); an CNPq bolsa de Produtividade em Pesquisa (Robert Morris); ERC Advanced Grant DMMCA, and a Trinity College JRF (Wojciech Samotij).

PY - 2014/1

Y1 - 2014/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84892683833&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84892683833&partnerID=8YFLogxK

U2 - 10.1112/plms/pdt033

DO - 10.1112/plms/pdt033

M3 - Article

AN - SCOPUS:84892683833

SN - 0024-6115

VL - 108

SP - 44

EP - 72

JO - Proceedings of the London Mathematical Society

JF - Proceedings of the London Mathematical Society

IS - 1

ER -