Hostname: page-component-78c5997874-dh8gc Total loading time: 0 Render date: 2024-11-20T04:25:56.387Z Has data issue: false hasContentIssue false
  • English
  • Français

The number of additive triples in subsets of abelian groups

Published online by Cambridge University Press:  26 January 2016

WOJCIECH SAMOTIJ  and
BENNY SUDAKOV
WOJCIECH SAMOTIJ
Affiliation:
School of Mathematical Sciences, Tel Aviv University, Tel Aviv 6997801, Israel. e-mail: [email protected]
BENNY SUDAKOV
Affiliation:
Department of Mathematics, ETH Zürich, 8092 Zürich, Switzerland. e-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

A set of elements of a finite abelian group is called sum-free if it contains no Schur triple, i.e., no triple of elements x, y, z with x + y = z. The study of how large the largest sum-free subset of a given abelian group is had started more than thirty years before it was finally resolved by Green and Ruzsa a decade ago. We address the following more general question. Suppose that a set A of elements of an abelian group G has cardinality a. How many Schur triples must A contain? Moreover, which sets of a elements of G have the smallest number of Schur triples? In this paper, we answer these questions for various groups G and ranges of a.

Type
Research Article
Information
Mathematical Proceedings of the Cambridge Philosophical Society , Volume 160 , Issue 3 , May 2016 , pp. 495 - 512
Copyright
Copyright © Cambridge Philosophical Society 2016 

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

REFERENCES

[1]Alon, N. and Chung, F. R. K.Explicit construction of linear sized tolerant networks. Proceedings of the First Japan Conference on Graph Theory and Applications (Hakone, 1986), vol. 72, 1988, pp. 15–19.CrossRefGoogle Scholar
[2]Balogh, J., Hu, P., Lidický, B., Pikhurko, O., Udvari, B. and Volec, J.Minimum number of monotone subsequences of length 4 in permutations. Combin. Probab. Comput. 24 (2015), 658–679.CrossRefGoogle Scholar
[3]Cauchy, A.Recherches sur les nombres. J. École Polytech. 9 (1813), 99–116.Google Scholar
[4]Clark, W. E., Dunning, L. A. and Rogers, D. G.Binary set functions and parity check matrices. Discrete Math. 80 (1990), 249–265.CrossRefGoogle Scholar
[5]Clark, W. E. and Pedersen, J.Sum-free sets in vector spaces over GF(2). J. Combin. Theory Ser. A 61 (1992), 222–229.CrossRefGoogle Scholar
[6]Conlon, D.On the Ramsey multiplicity of complete graphs. Combinatorica. 32 (2012), 171–186.CrossRefGoogle Scholar
[7]Das, S., Gan, W. and Sudakov, B. The minimum number of disjoint pairs in set systems and related problems. Combinatorica. to appear.Google Scholar
[8]Das, S., Gan, W. and Sudakov, B.Sperner's theorem and a problem of Erdős, Katona and Kleitman. Combin. Probab. Comput. 24 (2015), 585–608.CrossRefGoogle Scholar
[9]Davenport, H.On the addition of residue classes. J. London Math. Soc. 10 (1935), 30–32.CrossRefGoogle Scholar
[10]Diananda, P. H. and Yap, H. P.Maximal sum-free sets of elements of finite groups. Proc. Japan Acad. 45 (1969), 1–5.Google Scholar
[11]Dove, A. P., Griggs, J. R., Kang, R. J. and Sereni, J.-S.Supersaturation in the Boolean lattice. Integers 14A (2014), Paper No. A4, 7.Google Scholar
[12]Eberhard, S., Green, B. and Manners, F.Sets of integers with no large sum-free subset. Ann. of Math. (2) 180 (2014), 621–652.CrossRefGoogle Scholar
[13]Erdős, P.On a theorem of Rademacher-Turán. Illinois J. Math. 6 (1962), 122–127.CrossRefGoogle Scholar
[14]Erdős, P.Extremal problems in number theory. Proc. Sympos. Pure Math. Vol. VIII. Amer. Math. Soc., (Providence, R.I., 1965), pp. 181–189.Google Scholar
[15]Erdős, P.On the number of complete subgraphs and circuits contained in graphs. Časopis Pěst. Mat. 94 (1969), 290–296.CrossRefGoogle Scholar
[16]Erdős, P. and Kleitman, D. J.Extremal problems among subsets of a set. Discrete Math. 8 (1974), 281–294.CrossRefGoogle Scholar
[17]Erdős, P. and Simonovits, M.Supersaturated graphs and hypergraphs. Combinatorica. 3 (1983), 181–192.CrossRefGoogle Scholar
[18]Erdős, P. and Szekeres, G.A combinatorial problem in geometry. Compositio Math. 2 (1935), 463–470.Google Scholar
[19]Franek, F. and Rödl, V.2-colorings of complete graphs with a small number of monochromatic K4 subgraphs. Discrete Math. 114 (1993), 199–203, Combinatorics and algorithms (Jerusalem, 1988).CrossRefGoogle Scholar
[20]Green, B. and Ruzsa, I. Z.Sum-free sets in abelian groups. Israel J. Math. 147 (2005), 157–188.CrossRefGoogle Scholar
[21]Kemperman, J. H. B.On small sumsets in an abelian group. Acta Math. 103 (1960), 63–88.CrossRefGoogle Scholar
[22]Kleitman, D. J.A conjecture of Erdős-Katona on commensurable pairs among subsets of an n-set. Theory of Graphs (Proc. Colloq. Tihany, 1966), (Academic Press, New York, 1968), pp. 215–218.Google Scholar
[23]Kneser, M.Abschätzung der asymptotischen Dichte von Summenmengen. Math. Z. 58 (1953), 459–484.CrossRefGoogle Scholar
[24]Kneser, M.Ein Satz über abelsche Gruppen mit Anwendungen auf die Geometrie der Zahlen. Math. Z. 61 (1955), 429–434.CrossRefGoogle Scholar
[25]Lev, V. F., Łuczak, T. and Schoen, T.Sum-free sets in abelian groups. Israel J. Math. 125 (2001), 347–367.CrossRefGoogle Scholar
[26]Lovász, L. and Simonovits, M.On the Number of Complete Subgraphs of a Graph. II. Studies in Pure Mathematics, (Birkhäuser, Basel, 1983), pp. 459–495.CrossRefGoogle Scholar
[27]Myers, J. S.The minimum number of monotone subsequences. Electron. J. Combin. 9 (2002/03), no. 2, Research paper 4, 17 pp. (electronic), Permutation patterns (Otago, 2003).CrossRefGoogle Scholar
[28]Nazarewicz, E., O'Brien, M., O'Neill, M. and Staples, C.Equality in Pollard's theorem on set addition of congruence classes. Acta Arith. 127 (2007), 1–15.CrossRefGoogle Scholar
[29]Nikiforov, V.The number of cliques in graphs of given order and size. Trans. Amer. Math. Soc. 363 (2011), 1599–1618.CrossRefGoogle Scholar
[30]Pollard, J. M.A generalisation of the theorem of Cauchy and Davenport. J. London Math. Soc. (2) 8 (1974), 460–462.CrossRefGoogle Scholar
[31]Razborov, A. A.On the minimal density of triangles in graphs. Combin. Probab. Comput. 17 (2008), 603–618.CrossRefGoogle Scholar
[32]Reiher, C. The clique density theorem. arXiv:1212.2454v1 [math.CO].Google Scholar
[33]Rhemtulla, A. H. and Street, A. P.Maximal sum-free sets in finite abelian groups. Bull. Austral. Math. Soc. 2 (1970), 289–297.CrossRefGoogle Scholar
[34]Samotij, W. and Sudakov, B.On the number of monotone sequences. J. Combin. Theory Ser. B 115 (2015), 132–163.CrossRefGoogle Scholar
[35]Thomason, A.A disproof of a conjecture of Erdős in Ramsey theory. J. London Math. Soc. (2) 39 (1989), 246–255.CrossRefGoogle Scholar
[36]Yap, H. P.Maximal sum-free sets in finite abelian groups iv. Nanta Mathematica 5 (1972), 70–75.Google Scholar
[37]Yap, H. P.Maximal sum-free sets in finite abelian groups v. Bull. Austral. Math. Soc. 13 (1975), 337–342.CrossRefGoogle Scholar