TY - JOUR
T1 - A sharp bound on the number of maximal sum-free sets
AU - Balogh, József
AU - Liu, Hong
AU - Sharifzadeh, Maryam
AU - Treglown, Andrew
N1 - Publisher Copyright:
© 2015 Elsevier B.V.
PY - 2015/11
Y1 - 2015/11
N2 - Cameron and Erdős asked whether the number of maximal sum-free sets in {1,..., n} is much smaller than the number of sum-free sets. In the same paper they gave a lower bound of 2⌊n/4⌋ for the number of maximal sum-free sets. We prove the following: For each 1≤i≤4, there is a constant Ci such that, given any n≡i mod 4, {1,..., n} contains (Ci+o(1))2n/4 maximal sum-free sets. Our proof makes use of container and removal lemmas of Green, a structural result of Deshouillers, Freiman, Sós and Temkin and a recent bound on the number of subsets of integers with small sumset by Green and Morris.
AB - Cameron and Erdős asked whether the number of maximal sum-free sets in {1,..., n} is much smaller than the number of sum-free sets. In the same paper they gave a lower bound of 2⌊n/4⌋ for the number of maximal sum-free sets. We prove the following: For each 1≤i≤4, there is a constant Ci such that, given any n≡i mod 4, {1,..., n} contains (Ci+o(1))2n/4 maximal sum-free sets. Our proof makes use of container and removal lemmas of Green, a structural result of Deshouillers, Freiman, Sós and Temkin and a recent bound on the number of subsets of integers with small sumset by Green and Morris.
KW - Container method
KW - Independent sets
KW - Sum-free sets
UR - http://www.scopus.com/inward/record.url?scp=84947807826&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84947807826&partnerID=8YFLogxK
U2 - 10.1016/j.endm.2015.06.010
DO - 10.1016/j.endm.2015.06.010
M3 - Article
AN - SCOPUS:84947807826
SN - 1571-0653
VL - 49
SP - 57
EP - 64
JO - Electronic Notes in Discrete Mathematics
JF - Electronic Notes in Discrete Mathematics
ER -