A sharp bound on the number of maximal sum-free sets

Jozsef Balogh, Hong Liu, Maryam Sharifzadeh, Andrew Treglown

Research output: Chapter in Book/Report/Conference proceedingConference contribution

140 Downloads (Pure)

Abstract

Cameron and Erdős [P. Cameron and P. Erdős, Notes on sum-free and related sets, Combin. Probab.Comput., 8, (1999), 95–107] 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 [B. Green, The Cameron-Erdős conjecture, Bull. London Math. Soc., 36, (2004), 769–778; B. Green, A Szemerédi-type regularity lemma in abelian groups, with applications, Geom. Funct. Anal., 15, (2005), 340–376], a structural result of Deshouillers, Freiman, Sós and Temkin [J. Deshouillers, G. Freiman, V. Sós and M. Temkin, On the structure of sumfree sets II, Astérisque, 258, (1999), 149–161] and a recent bound on the number of subsets of integers with small sumset by Green and Morris [B. Green, R. Morris, Counting sets with small sumset and applications, Combinatorica, to appear].
Original languageEnglish
Title of host publicationElectronic Notes in Discrete Mathematics
PublisherElsevier
Pages57-64
Volume49
DOIs
Publication statusPublished - Nov 2015

Keywords

  • Sum-free sets
  • Independent sets
  • Container method

Fingerprint

Dive into the research topics of 'A sharp bound on the number of maximal sum-free sets'. Together they form a unique fingerprint.

Cite this