Hostname: page-component-74656f9884-8r8nv Total loading time: 0 Render date: 2026-11-08T14:27:17.834Z Has data issue: false hasContentIssue false
  • English
  • Français

The Sharp Threshold for Maximum-Size Sum-Free Subsets in Even-Order Abelian Groups

Part of: Extremal combinatorics Additive number theory; partitions

Published online by Cambridge University Press:  09 January 2015

NEAL BUSHAW ,
MAURÍCIO COLLARES NETO ,
ROBERT MORRIS  and
PAUL SMITH
NEAL BUSHAW
Affiliation:
School of Mathematics and Statistics, Arizona State University, Tempe, AZ 85287, USA (e-mail: neal@asu.edu)
MAURÍCIO COLLARES NETO
Affiliation:
IMPA, Estrada Dona Castorina 110, Jardim Botânico, Rio de Janeiro, RJ, Brazil (e-mail: collares@impa.br, rob@impa.br, psmith@impa.br)
ROBERT MORRIS
Affiliation:
IMPA, Estrada Dona Castorina 110, Jardim Botânico, Rio de Janeiro, RJ, Brazil (e-mail: collares@impa.br, rob@impa.br, psmith@impa.br)
PAUL SMITH
Affiliation:
IMPA, Estrada Dona Castorina 110, Jardim Botânico, Rio de Janeiro, RJ, Brazil (e-mail: collares@impa.br, rob@impa.br, psmith@impa.br)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We study sum-free sets in sparse random subsets of even-order abelian groups. In particular, we determine the sharp threshold for the following property: the largest such set is contained in some maximum-size sum-free subset of the group. This theorem extends recent work of Balogh, Morris and Samotij, who resolved the case G = ℤ2n, and who obtained a weaker threshold (up to a constant factor) in general.

MSC classification

Primary: 05D40: Probabilistic methods
Secondary: 11P99: None of the above, but in this section

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 24 , Special Issue 4: Oberwolfach Special Issue Part 1 , July 2015 , pp. 609 - 640
Copyright
Copyright © Cambridge University Press 2015 

References

[1]Alon, N., Balogh, J., Morris, R. and Samotij, W. (2014) Counting sum-free subsets in Abelian groups. Israel J. 199 309–344.CrossRefGoogle Scholar
[2]Alon, N., Balogh, J., Morris, R. and Samotij, W. (2014) A refinement of the Cameron–Erdős conjecture. Proc. London Math. Soc. 108 44–72.CrossRefGoogle Scholar
[3]Alon, N. and Kleitman, D. J. (1990) Sum-free subsets. In A Tribute to Paul Erdős (Baker, A., Bollobás, B. and Hajnal, A., eds), Cambridge University Press, pp. 13–26.CrossRefGoogle Scholar
[4]Alon, N. and Spencer, J. (2008) The Probabilistic Method, third edition, Wiley-Interscience.CrossRefGoogle Scholar
[5]Babai, L., Simonovits, M. and Spencer, J. (1990) Extremal subgraphs of random graphs. J. Graph Theory 14 599–622.CrossRefGoogle Scholar
[6]Balogh, J., Morris, R. and Samotij, W. (2014) Random sum-free subsets of abelian groups. Israel J. 199 651–685.CrossRefGoogle Scholar
[7]Balogh, J., Morris, R. and Samotij, W. Independent sets in hypergraphs. J. Amer. Math. Soc., to appear.Google Scholar
[8]Balogh, J., Morris, R., Samotij, W. and Warnke, L. The typical structure of sparse K r+1-free graphs. Trans. Amer. Math. Soc., to appear.Google Scholar
[9]Bollobás, B. and Thomason, A. (1986) Threshold functions. Combinatorica 7 35–38.CrossRefGoogle Scholar
[10]Chvátal, V. (1979) The tail of the hypergeometric distribution Discrete Math. 25 285–287.CrossRefGoogle Scholar
[11]Conlon, D. and Gowers, W. T. Combinatorial theorems in sparse random sets. Submitted.Google Scholar
[12]DeMarco, B. and Kahn, J. Mantel's theorem for random graphs. Random Struct. Alg., to appear.Google Scholar
[13]Diananda, P. H. and Yap, H. P. (1969) Maximal sum-free sets of elements of finite groups. Proc. Japan Acad. 45 1–5.Google Scholar
[14]Frankl, P. and Rödl, V. (1986) Large triangle-free subgraphs in graphs without K 4. Graphs Combin. 2 135–144.CrossRefGoogle Scholar
[15]Friedgut, E. (1999) Sharp thresholds of graph properties, and the k-sat problem, with an appendix by Jean Bourgain. J. Amer. Math. Soc. 12 1017–1054.CrossRefGoogle Scholar
[16]Friedgut, E., Rödl, V., Ruciński, A. and Tetali, P. (2006) A Sharp Threshold for Random Graphs with a Monochromatic Triangle in Every Edge Coloring, Vol. 179 of Memoirs of the American Mathematical Society.CrossRefGoogle Scholar
[17]Friedgut, E., Rödl, V. and Schacht, M. (2010) Ramsey properties of random discrete structures. Random Struct. Alg. 37 407–436.CrossRefGoogle Scholar
[18]Graham, R., Rödl, V. and Ruciński, A. (1996) On Schur properties of random subsets of integers. J. Number Theory 61 388–408.CrossRefGoogle Scholar
[19]Green, B. (2004) The Cameron–Erdős conjecture. Bull. London Math. Soc. 36 769–778.CrossRefGoogle Scholar
[20]Green, B. and Ruzsa, I. Z. (2005) Sum-free sets in abelian groups. Israel J. Math. 147 157–189.CrossRefGoogle Scholar
[21]Hatami, H. (2012) A structure theorem for Boolean functions with small total influences. Ann. Math. 176 509–533.CrossRefGoogle Scholar
[22]Janson, S., Łuczak, T. and Ruciński, A. (2000) Random Graphs, Wiley.CrossRefGoogle Scholar
[23]Kohayakawa, Y., Łuczak, T. and Rödl, V. (1996) Arithmetic progressions of length three in subsets of a random set. Acta Arith. 75 133–163.CrossRefGoogle Scholar
[24]Lev, V. F.Łuczak, T. and Schoen, T. (2001) Sum-free sets in abelian groups. Israel J. Math. 125 347–367.CrossRefGoogle Scholar
[25]Rödl, V. and Ruciński, A. (1995) Threshold functions for Ramsey properties. J. Amer. Math. Soc. 8 917–942.CrossRefGoogle Scholar
[26]Rödl, V. and Ruciński, A. (1997) Rado partition theorem for random subsets of integers Proc. London Math. Soc. 74 481–502.CrossRefGoogle Scholar
[27]Samotij, W. (2014) Stability results for random discrete structures. Random Struct. Alg. 44 269–289.CrossRefGoogle Scholar
[28]Sapozhenko, A. A. (2002) Asymptotics of the number of sum-free sets in abelian groups of even order (in Russian). Dokl. Akad. Nauk. 383 454–457.Google Scholar
[29]Sapozhenko, A. A. (2003) The Cameron–Erdős conjecture (in Russian). Dokl. Akad. Nauk. 393 749–752.Google Scholar
[30]Saxton, D. and Thomason, A. Hypergraph containers. Submitted.Google Scholar
[31]Schacht, M. Extremal results for random discrete structures. Submitted.Google Scholar
[32]Schur, I. (1916) Über die Kongruenz xm + ym ≡ zm (mod p). Jahresber. Deutsche Math.-Verein. 25 114–117.Google Scholar
[33]Warnke, L. On the method of typical bounded differences. To appear in CPC.Google Scholar