Skip to main content
SpringerLink
Log in

Counting sum-free sets in abelian groups

  • Published:
Israel Journal of Mathematics Aims and scope Submit manuscript

Abstract

In this paper we study sum-free sets of order m in finite abelian groups. We prove a general theorem about independent sets in 3-uniform hypergraphs, which allows us to deduce structural results in the sparse setting from stability results in the dense setting. As a consequence, we determine the typical structure and asymptotic number of sum-free sets of order m in abelian groups G whose order n is divisible by a prime q with q ≡ 2 (mod 3), for every m ⩾ \(C(q)\sqrt {n\log n} \), thus extending and refining a theorem of Green and Ruzsa. In particular, we prove that almost all sumfree subsets of size m are contained in a maximum-size sum-free subset of G. We also give a completely self-contained proof of this statement for abelian groups of even order, which uses spectral methods and a new bound on the number of independent sets of a fixed size in an (n, d, λ)-graph.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. N. Alon, Independent sets in regular graphs and sum-free subsets of finite groups, Israel Journal of Mathematics 73 (1991), 247–256.

    Article  MATH  MathSciNet  Google Scholar 

  2. N. Alon, J. Balogh, R. Morris and W. Samotij, A refinement of the Cameron-Erdős Conjecture, Proceedings of the London Mathematical Society, to appear.

  3. N. Alon and F. R. K. Chung, Explicit construction of linear sized tolerant networks, Discrete Mathematics 72 (1988), Proceedings of the First Japan Conference on Graph Theory and Applications (Hakone, 1986), 15–19.

    Article  MATH  MathSciNet  Google Scholar 

  4. N. Alon and V. Rödl, Sharp bounds for some multicolor Ramsey numbers, Combinatorica 25 (2005), 125–141.

    Article  MATH  MathSciNet  Google Scholar 

  5. N. Alon and J. H. Spencer, The Probabilistic Method, third edn., Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons Inc., Hoboken, NJ, 2008, With an appendix on the life and work of Paul Erdős.

    Book  MATH  Google Scholar 

  6. L. Babai, M. Simonovits and J. Spencer, Extremal subgraphs of random graphs, Journal of Graph Theory 14 (1990), 599–622.

    Article  MATH  MathSciNet  Google Scholar 

  7. J. Balogh, R. Morris and W. Samotij, Independent sets in hypergraphs, arXiv:1204.6530v1 [math.CO].

  8. J. Balogh, R. Morris and W. Samotij, Random sum-free subsets of abelian groups, Israel Journal of Mathematics, to appear.

  9. J. Balogh and W. Samotij, The number of K m,m-free graphs, Combinatorica 31 (2011), 131–150.

    Article  MATH  MathSciNet  Google Scholar 

  10. J. Balogh and W. Samotij, The number of K s,t-free graphs, Journal of the London Mathematical Society 83 (2011), 368–388.

    Article  MATH  MathSciNet  Google Scholar 

  11. T. Carroll, D. Galvin and P. Tetali, Matchings and independent sets of a fixed size in regular graphs, Journal of Combinatorial Theory. Series A 116 (2009), 1219–1227.

    Article  MATH  MathSciNet  Google Scholar 

  12. D. Conlon and T. Gowers, Combinatorial theorems in sparse random sets, arXiv:1011.4310v1 [math.CO].

  13. P. H. Diananda and H. P. Yap, Maximal sum-free sets of elements of finite groups, Proceedings of the Japan Academy 45 (1969), 1–5.

    Article  MATH  MathSciNet  Google Scholar 

  14. P. Erdős, Some recent results on extremal problems in graph theory. Results, in Theory of Graphs (Internat. Sympos., Rome, 1966), (P. Rosenstiehl, ed.), Gordon and Breach, New York, 1967, pp. 117–123 (English); Dunod, Paris, pp. 124–130 (French).

    Google Scholar 

  15. P. Erdős, D. J. Kleitman and B. L. Rothschild, Asymptotic enumeration of Kn-free graphs, in Colloquio Internazionale sulle Teorie Combinatorie (Rome, 1973), Tomo II, Accad. Naz. Lincei, Rome, 1976, pp. 19–27. Atti dei Convegni Lincei, No. 17.

    Google Scholar 

  16. P. Erdős and A. H. Stone, On the structure of linear graphs, Bulletin of the American Mathematical Society 52 (1946), 1087–1091.

    Article  MathSciNet  Google Scholar 

  17. P. Frankl and V. Rödl, Large triangle-free subgraphs in graphs without K 4, Graphs and Combinatorics 2 (1986), 135–144.

    Article  MATH  MathSciNet  Google Scholar 

  18. E. Friedgut, V. Rödl, A. Ruciński and P. Tetali, A sharp threshold for random graphs with a monochromatic triangle in every edge coloring, Memoirs of the American Mathematical Society 179 (2006).

  19. D. Galvin and J. Kahn, On phase transition in the hard-core model on Zd, Combinatorics, Probability and Computing 13 (2004), 137–164.

    Article  MATH  MathSciNet  Google Scholar 

  20. R. Graham, V. Rödl and A. Ruciński, On Schur properties of random subsets of integers, Journal of Number Theory 61 (1996), 388–408.

    Article  MATH  MathSciNet  Google Scholar 

  21. B. Green and I. Z. Ruzsa, Sum-free sets in abelian groups, Israel Journal of Mathematics 147 (2005), 157–188.

    Article  MATH  MathSciNet  Google Scholar 

  22. Alan J. Hoffman, On eigenvalues and colorings of graphs, in Graph Theory and its Applications (Proc. Advanced Sem., Math. Research Center, Univ. of Wisconsin, Madison, Wis., 1969), Academic Press, New York, 1970, pp. 79–91.

    Google Scholar 

  23. S. Hoory, N. Linial and A. Wigderson, Expander graphs and their applications, Bulletin of the American Mathematical Society 43 (2006), 439–561 (electronic).

    Article  MATH  MathSciNet  Google Scholar 

  24. S. Janson, T. Łuczak and A. Rucinski, Random Graphs, Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley-Interscience, New York, 2000.

    Google Scholar 

  25. J. Kahn, An entropy approach to the hard-core model on bipartite graphs, Combinatorics, Probability and Computation 10 (2001), 219–237.

    MATH  MathSciNet  Google Scholar 

  26. J. Kahn, Entropy, independent sets and antichains: a new approach to Dedekind’s problem, Proceedings of the American Mathematical Society 130 (2002), 371–378.

    Article  MATH  MathSciNet  Google Scholar 

  27. D. J. Kleitman and K. J. Winston, On the number of graphs without 4-cycles, Discrete Mathematics 41 (1982), 167–172.

    Article  MATH  MathSciNet  Google Scholar 

  28. Y. Kohayakawa, S. Lee, V. Rödl and W. Samotij, The number of Sidon sets and the maximum size of Sidon sets contained in a sparse random set of integers, Random Structures Algorithms, to appear.

  29. Y. Kohayakawa, T. Łuczak and V. Rödl, Arithmetic progressions of length three in subsets of a random set, Acta Arithmetica 75 (1996), 133–163.

    MATH  MathSciNet  Google Scholar 

  30. Ph. G. Kolaitis, H. J. Prömel and B. L. Rothschild, K l+1-free graphs: asymptotic structure and a 0−1 law, Transactions of the American Mathematical Society 303 (1987), 637–671.

    MATH  MathSciNet  Google Scholar 

  31. V. F. Lev, T. Łuczak and T. Schoen, Sum-free sets in abelian groups, Israel Journal of Mathematics 125 (2001), 347–367.

    Article  MATH  MathSciNet  Google Scholar 

  32. D. Osthus, H. J. Prömel and A. Taraz, For which densities are random triangle-free graphs almost surely bipartite?, Combinatorica 23 (2003), 105–150, Paul Erdős and his mathematics (Budapest, 1999).

    Article  MATH  MathSciNet  Google Scholar 

  33. R. Peled and W. Samotij, Odd cutsets and the hard-core model on ℤd, Annales de l’Institut Henri Poincaré. Probabilités et Statistiques, to appear.

  34. H. J. Prömel and A. Steger, On the asymptotic structure of sparse triangle free graphs, Journal of Graph Theory 21 (1996), 137–151.

    Article  MATH  MathSciNet  Google Scholar 

  35. V. Rödl and A. Ruciński, Threshold functions for Ramsey properties, Journal of the American Mathematical Society 8 (1995), 917–942.

    Article  MATH  MathSciNet  Google Scholar 

  36. V. Rödl and A. Ruciński, Rado partition theorem for random subsets of integers, Proceedings of the London Mathematical Society 74 (1997), 481–502.

    Article  MATH  MathSciNet  Google Scholar 

  37. A. A. Sapozhenko, On the number of independent sets in extenders, DiskretnayaMatematika 13 (2001), 56–62.

  38. A. A. Sapozhenko, Asymptotics of the number of sum-free sets in abelian groups of even order, Rossiĭskaya Akademiya Nauk. Dokladi Akademii Nauk 383 (2002), 454–457.

    MathSciNet  Google Scholar 

  39. D. Saxton and A. Thomason, Hypergraph containers, arXiv:1204.6595v2 [math.CO].

  40. M. Schacht, Extremal results for random discrete structures, submitted.

  41. M. Simonovits, A method for solving extremal problems in graph theory, stability problems, in Theory of Graphs (Proc. Colloq., Tihany, 1966), Academic Press, New York, 1968, pp. 279–319.

    Google Scholar 

  42. E. Szemerédi, On sets of integers containing no k elements in arithmetic progression, Acta Arithmetica 27 (1975), 199–245.

    MATH  MathSciNet  Google Scholar 

  43. P. Turán, Eine Extremalaufgabe aus der Graphentheorie, Matematikai és Fizikai Lapok 48 (1941), 436–452.

    Google Scholar 

  44. Y. Zhao, The number of independent sets in a regular graph, Combinatorics, Probability and Computing 19 (2010), 315–320.

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Mathematical Sciences, Tel Aviv University, Tel Aviv, 69978, Israel

    Noga Alon

  2. Department of Mathematics, University of Illinois, 1409 W. Green Street, Urbana, IL, 61801, USA

    József Balogh

  3. IMPA, Estrada Dona Castorina 110, Jardim Botânico, Rio de Janeiro, RJ, Brasil

    Robert Morris

  4. School of Mathematical Sciences, Tel Aviv University, Tel Aviv, 69978, Israel

    Wojciech Samotij

  5. Trinity College, Cambridge, CB2 1TQ, UK

    Wojciech Samotij

Authors
  1. Noga Alon
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. József Balogh
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Robert Morris
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Wojciech Samotij
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Noga Alon.

Additional information

Research supported in part by: (NA) ERC Advanced Grant DMMCA, a USA-Israeli BSF grant and the Israeli I-Core program; (JB) NSF CAREER Grant DMS-0745185, UIUC Campus Research Board Grant 11067, and OTKA Grant K76099; (RM) a CNPq bolsa de Produtividade em Pesquisa; (WS) ERC Advanced Grant DMMCA and a Trinity College JRF.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Alon, N., Balogh, J., Morris, R. et al. Counting sum-free sets in abelian groups. Isr. J. Math. 199, 309–344 (2014). https://doi.org/10.1007/s11856-013-0067-y

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11856-013-0067-y

Keywords

Search

Navigation