Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

 
 

 

The number of maximal sum-free subsets of integers


Authors: József Balogh, Hong Liu, Maryam Sharifzadeh and Andrew Treglown
Journal: Proc. Amer. Math. Soc. 143 (2015), 4713-4721
MSC (2010): Primary 11B75; Secondary 05C69
DOI: https://doi.org/10.1090/S0002-9939-2015-12615-9
Published electronically: April 2, 2015
MathSciNet review: 3391030
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] 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, https://doi.org/10.1112/plms/pdt033
  • [2] J. Balogh, H. Liu, M. Sharifzadeh and A. Treglown,
    Sharp bound on the number of maximal sum-free subsets of integers,
    manuscript.
  • [3] J. Balogh, R. Morris and W. Samotij,
    Independent sets in hypergraphs,
    J. Amer. Math. Soc., to appear.
  • [4] 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, https://doi.org/10.1112/blms/bdu059
  • [5] 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 (92g:11010)
  • [6] 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 (2000c:05144), https://doi.org/10.1017/S0963548398003435
  • [7] 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 (2001i:11011)
  • [8] Ben Green, The Cameron-Erdős conjecture, Bull. London Math. Soc. 36 (2004), no. 6, 769-778. MR 2083752 (2005g:11027), https://doi.org/10.1112/S0024609304003650
  • [9] B. Green, A Szemerédi-type regularity lemma in abelian groups, with applications, Geom. Funct. Anal. 15 (2005), no. 2, 340-376. MR 2153903 (2006e:11029), https://doi.org/10.1007/s00039-005-0509-8
  • [10] 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 (2005g:11028), https://doi.org/10.1556/SScMath.41.2004.3.2
  • [11] 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 (94i:05047), https://doi.org/10.1137/0406022
  • [12] L. Ilinca and J. Kahn, Counting maximal antichains and independent sets, Order 30 (2013), no. 2, 427-435. MR 3063196, https://doi.org/10.1007/s11083-012-9253-5
  • [13] 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 (2010f:20028), https://doi.org/10.1016/j.jcta.2008.12.003
  • [14] Tomasz Łuczak and Tomasz Schoen, On the number of maximal sum-free sets, Proc. Amer. Math. Soc. 129 (2001), no. 8, 2205-2207 (electronic). MR 1823901 (2002a:11015), https://doi.org/10.1090/S0002-9939-00-05815-9
  • [15] J. W. Moon and L. Moser, On cliques in graphs, Israel J. Math. 3 (1965), 23-28. MR 0182577 (32 #60)
  • [16] A. A. Sapozhenko, The Cameron-Erdős conjecture, Dokl. Akad. Nauk 393 (2003), no. 6, 749-752 (Russian). MR 2088503 (2006a:11027)
  • [17] 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 (2006e:05129)
  • [18] D. Saxton and A. Thomason,
    Hypergraph containers,
    preprint.
  • [19] I. Schur,
    Uber die Kongruenz $ x^m +y^m \equiv z^m$ (mod $ p$),
    ber. Deutsch. Mat. Verein., 25, (1916), 114-117.
  • [20] Guy Wolfovitz, Bounds on the number of maximal sum-free sets, European J. Combin. 30 (2009), no. 7, 1718-1723. MR 2548662 (2010m:05034), https://doi.org/10.1016/j.ejc.2009.03.015

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2010): 11B75, 05C69

Retrieve articles in all journals with MSC (2010): 11B75, 05C69


Additional Information

József Balogh
Affiliation: Department of Mathematics, University of Illinois, Urbana, Illinois 61801 — and — Bolyai Institute, University of Szeged, Szeged, Hungary
Email: jobal@math.uiuc.edu

Hong Liu
Affiliation: Department of Mathematics, University of Illinois, Urbana, Illinois 61801
Email: hliu36@illinois.edu

Maryam Sharifzadeh
Affiliation: Department of Mathematics, University of Illinois, Urbana, Illinois 61801
Email: sharifz2@illinois.edu

Andrew Treglown
Affiliation: School of Mathematics, University of Birmingham, United Kingdom
Email: a.c.treglown@bham.ac.uk

DOI: https://doi.org/10.1090/S0002-9939-2015-12615-9
Received by editor(s): May 12, 2014
Received by editor(s) in revised form: July 19, 2014, July 22, 2014, and August 25, 2014
Published electronically: April 2, 2015
Additional Notes: The authors’ research was partially supported by Simons Fellowship, NSF CAREER Grant DMS-0745185, Arnold O. Beckman Research Award (UIUC Campus Research Board 13039) and Marie Curie FP7-PEOPLE-2012-IIF 327763.
Communicated by: Patricia L. Hersh
Article copyright: © Copyright 2015 American Mathematical Society

American Mathematical Society