Hostname: page-component-cd9895bd7-dk4vv Total loading time: 0 Render date: 2024-12-28T00:34:51.476Z 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: Additive number theory; partitions Extremal combinatorics

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: [email protected])
MAURÍCIO COLLARES NETO
Affiliation:
IMPA, Estrada Dona Castorina 110, Jardim Botânico, Rio de Janeiro, RJ, Brazil (e-mail: [email protected], [email protected], [email protected])
ROBERT MORRIS
Affiliation:
IMPA, Estrada Dona Castorina 110, Jardim Botânico, Rio de Janeiro, RJ, Brazil (e-mail: [email protected], [email protected], [email protected])
PAUL SMITH
Affiliation:
IMPA, Estrada Dona Castorina 110, Jardim Botânico, Rio de Janeiro, RJ, Brazil (e-mail: [email protected], [email protected], [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

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
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 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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