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 -