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 -