×

Counting sum-free sets in abelian groups. (English) Zbl 1332.11030

In this paper, sum-free sets of order \(m\) in finite abelian groups are studied. Sum-free subsets of abelian groups are central objects of interest in Additive Combinatorics, and have been studied intensively in recent years. The main questions are as follows: What are the largest sum-free subsets of a group? How many sum-free sets are there? And what does a typical such set look like?
The main results obtained in this paper are the following:
Theorem 1.1. For every prime \(q\equiv 2\pmod 3\), there exists a constant \(C(q)>0\) such that the following holds. Let \(G\) be an abelian group of Type I(\(q\)) and order \(n\), and let \(m\geq C(q)\sqrt{n\log n}\). Then almost every sum-free subset of \(G\) of size \(m\) is contained in a maximum-size sum-free subset of \(G\), and hence \[ |SF(G,m)|=\lambda _{q}(\#\{\text{elements\, of\, \(G\)\, of\, order\, \(q\)}\}+o(1))\left( \begin{matrix} \mu (G)n \\ m \end{matrix} \right)\quad\text{as }n\to \infty, \] where \(\lambda _{q}=1\) if \(q=2\) and \( \lambda _{q}=1/2\) otherwise.
and
{Theorem 1.3} For every \(\varepsilon >0\), there exists a constant \( C=C(\varepsilon )\) such that the following holds. If \(\mathcal{G}\) is an \(n\) -vertex \(d\)-regular graph with \(\lambda (\mathcal{G})\geq -\lambda \), then \[ I(G,m)\leq \left( \begin{matrix} (\frac{\lambda }{d+\lambda }+\varepsilon )n \\ m \end{matrix} \right) \] for every \(m\geq Cn/d\).
There is a very elaborate description of the historical context of such problems (including a large Bibliography).

MSC:

11B75 Other combinatorial number theory
11B13 Additive bases, including sumsets
20K01 Finite abelian groups
05D10 Ramsey theory
PDF BibTeX XML Cite
Full Text: DOI arXiv

References:

[1] N. Alon, Independent sets in regular graphs and sum-free subsets of finite groups, Israel Journal of Mathematics 73 (1991), 247–256. · Zbl 0762.05050
[2] N. Alon, J. Balogh, R. Morris and W. Samotij, A refinement of the Cameron-Erdos Conjecture, Proceedings of the London Mathematical Society, to appear. · Zbl 1284.05024
[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. · Zbl 0657.05068
[4] N. Alon and V. Rödl, Sharp bounds for some multicolor Ramsey numbers, Combinatorica 25 (2005), 125–141. · Zbl 1090.05049
[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 Erdos.
[6] L. Babai, M. Simonovits and J. Spencer, Extremal subgraphs of random graphs, Journal of Graph Theory 14 (1990), 599–622. · Zbl 0738.05048
[7] J. Balogh, R. Morris and W. Samotij, Independent sets in hypergraphs, arXiv:1204.6530v1 [math.CO]. · Zbl 1310.05154
[8] J. Balogh, R. Morris and W. Samotij, Random sum-free subsets of abelian groups, Israel Journal of Mathematics, to appear. · Zbl 1370.11040
[9] J. Balogh and W. Samotij, The number of K m,m-free graphs, Combinatorica 31 (2011), 131–150. · Zbl 1249.05190
[10] J. Balogh and W. Samotij, The number of K s,t-free graphs, Journal of the London Mathematical Society 83 (2011), 368–388. · Zbl 1227.05170
[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. · Zbl 1243.05193
[12] D. Conlon and T. Gowers, Combinatorial theorems in sparse random sets, arXiv:1011.4310v1 [math.CO]. · Zbl 1351.05204
[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. · Zbl 0179.04801
[14] P. Erdos, 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).
[15] P. Erdos, 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.
[16] P. Erdos and A. H. Stone, On the structure of linear graphs, Bulletin of the American Mathematical Society 52 (1946), 1087–1091. · Zbl 0063.01277
[17] P. Frankl and V. Rödl, Large triangle-free subgraphs in graphs without K 4, Graphs and Combinatorics 2 (1986), 135–144. · Zbl 0596.05037
[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). · Zbl 1087.05052
[19] D. Galvin and J. Kahn, On phase transition in the hard-core model on Zd, Combinatorics, Probability and Computing 13 (2004), 137–164. · Zbl 1151.82374
[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. · Zbl 0880.05081
[21] B. Green and I. Z. Ruzsa, Sum-free sets in abelian groups, Israel Journal of Mathematics 147 (2005), 157–188. · Zbl 1158.11311
[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.
[23] S. Hoory, N. Linial and A. Wigderson, Expander graphs and their applications, Bulletin of the American Mathematical Society 43 (2006), 439–561 (electronic). · Zbl 1147.68608
[24] S. Janson, T. Łuczak and A. Rucinski, Random Graphs, Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley-Interscience, New York, 2000.
[25] J. Kahn, An entropy approach to the hard-core model on bipartite graphs, Combinatorics, Probability and Computation 10 (2001), 219–237. · Zbl 0985.60088
[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. · Zbl 0982.05014
[27] D. J. Kleitman and K. J. Winston, On the number of graphs without 4-cycles, Discrete Mathematics 41 (1982), 167–172. · Zbl 0491.05035
[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. · Zbl 1402.11021
[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. · Zbl 0858.11009
[30] Ph. G. Kolaitis, H. J. Prömel and B. L. Rothschild, K l+1-free graphs: asymptotic structure and a 0 law, Transactions of the American Mathematical Society 303 (1987), 637–671. · Zbl 0641.05025
[31] V. F. Lev, T. Łuczak and T. Schoen, Sum-free sets in abelian groups, Israel Journal of Mathematics 125 (2001), 347–367. · Zbl 1055.20043
[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 Erdos and his mathematics (Budapest, 1999). · Zbl 1047.05040
[33] R. Peled and W. Samotij, Odd cutsets and the hard-core model on \(\mathbb{Z}\)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. · Zbl 0856.05037
[35] V. Rödl and A. Ruciński, Threshold functions for Ramsey properties, Journal of the American Mathematical Society 8 (1995), 917–942. · Zbl 0846.05079
[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. · Zbl 0880.05080
[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.
[39] D. Saxton and A. Thomason, Hypergraph containers, arXiv:1204.6595v2 [math.CO]. · Zbl 1320.05085
[40] M. Schacht, Extremal results for random discrete structures, submitted. · Zbl 1351.05207
[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.
[42] E. Szemerédi, On sets of integers containing no k elements in arithmetic progression, Acta Arithmetica 27 (1975), 199–245. · Zbl 0303.10056
[43] P. Turán, Eine Extremalaufgabe aus der Graphentheorie, Matematikai és Fizikai Lapok 48 (1941), 436–452.
[44] Y. Zhao, The number of independent sets in a regular graph, Combinatorics, Probability and Computing 19 (2010), 315–320. · Zbl 1215.05140
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.