The number of maximal sum-free subsets of integers

Balogh, József; Liu, Hong; Sharifzadeh, Maryam; Treglown, Andrew

doi:10.1090/S0002-9939-2015-12615-9

The number of maximal sum-free subsets of integers
HTML articles powered by AMS MathViewer

by József Balogh, Hong Liu, Maryam Sharifzadeh and Andrew Treglown PDF

Proc. Amer. Math. Soc. 143 (2015), 4713-4721 Request permission

Abstract:

Cameron and Erdős raised the question of how many maximal sum-free sets there are in $\{1, \dots , n\}$, giving a lower bound of $2^{\lfloor n/4 \rfloor }$. In this paper we prove that there are in fact at most $2^{(1/4+o(1))n}$ maximal sum-free sets in $\{1, \dots , n\}$. Our proof makes use of container and removal lemmas of Green as well as a result of Deshouillers, Freiman, Sós and Temkin on the structure of sum-free sets.

References

Noga Alon, József Balogh, Robert Morris, and Wojciech Samotij, A refinement of the Cameron-Erdős conjecture, Proc. Lond. Math. Soc. (3) 108 (2014), no. 1, 44–72. MR 3162820, DOI 10.1112/plms/pdt033
J. Balogh, H. Liu, M. Sharifzadeh and A. Treglown, Sharp bound on the number of maximal sum-free subsets of integers, manuscript.
J. Balogh, R. Morris and W. Samotij, Independent sets in hypergraphs, J. Amer. Math. Soc., to appear.
József Balogh and Šárka Petříčková, The number of the maximal triangle-free graphs, Bull. Lond. Math. Soc. 46 (2014), no. 5, 1003–1006. MR 3262201, DOI 10.1112/blms/bdu059
P. J. Cameron and P. Erdős, On the number of sets of integers with various properties, Number theory (Banff, AB, 1988) de Gruyter, Berlin, 1990, pp. 61–79. MR 1106651
Peter J. Cameron and Paul Erdős, Notes on sum-free and related sets, Combin. Probab. Comput. 8 (1999), no. 1-2, 95–107. Recent trends in combinatorics (Mátraháza, 1995). MR 1684624, DOI 10.1017/S0963548398003435
Jean-Marc Deshouillers, Gregory A. Freiman, Vera Sós, and Mikhail Temkin, On the structure of sum-free sets. II, Astérisque 258 (1999), xii, 149–161 (English, with English and French summaries). Structure theory of set addition. MR 1701193
Ben Green, The Cameron-Erdős conjecture, Bull. London Math. Soc. 36 (2004), no. 6, 769–778. MR 2083752, DOI 10.1112/S0024609304003650
B. Green, A Szemerédi-type regularity lemma in abelian groups, with applications, Geom. Funct. Anal. 15 (2005), no. 2, 340–376. MR 2153903, DOI 10.1007/s00039-005-0509-8
B. Green and I. Z. Ruzsa, Counting sumsets and sum-free sets modulo a prime, Studia Sci. Math. Hungar. 41 (2004), no. 3, 285–293. MR 2082746, DOI 10.1556/SScMath.41.2004.3.2
Mihály Hujter and Zsolt Tuza, The number of maximal independent sets in triangle-free graphs, SIAM J. Discrete Math. 6 (1993), no. 2, 284–288. MR 1215234, DOI 10.1137/0406022
L. Ilinca and J. Kahn, Counting maximal antichains and independent sets, Order 30 (2013), no. 2, 427–435. MR 3063196, DOI 10.1007/s11083-012-9253-5
Daniel Král, Oriol Serra, and Lluís Vena, A combinatorial proof of the removal lemma for groups, J. Combin. Theory Ser. A 116 (2009), no. 4, 971–978. MR 2513645, DOI 10.1016/j.jcta.2008.12.003
Tomasz Łuczak and Tomasz Schoen, On the number of maximal sum-free sets, Proc. Amer. Math. Soc. 129 (2001), no. 8, 2205–2207. MR 1823901, DOI 10.1090/S0002-9939-00-05815-9
J. W. Moon and L. Moser, On cliques in graphs, Israel J. Math. 3 (1965), 23–28. MR 182577, DOI 10.1007/BF02760024
A. A. Sapozhenko, The Cameron-Erdős conjecture, Dokl. Akad. Nauk 393 (2003), no. 6, 749–752 (Russian). MR 2088503
A. A. Sapozhenko, On the number of independent sets in graphs, Problems of theoretical cybernetics, Kazan. Gos. Univ., Kazan′2004, pp. 85–93 (Russian, with Russian summary). MR 2161000
D. Saxton and A. Thomason, Hypergraph containers, preprint.
I. Schur, Uber die Kongruenz $x^m +y^m \equiv z^m$ (mod $p$), ber. Deutsch. Mat. Verein., 25, (1916), 114–117.
Guy Wolfovitz, Bounds on the number of maximal sum-free sets, European J. Combin. 30 (2009), no. 7, 1718–1723. MR 2548662, DOI 10.1016/j.ejc.2009.03.015