Hostname: page-component-745bb68f8f-b95js Total loading time: 0 Render date: 2025-02-11T21:40:27.278Z Has data issue: false hasContentIssue false
  • English
  • Français

On the Number of Bh-Sets

Part of: Sequences and sets Combinatorics Extremal combinatorics

Published online by Cambridge University Press:  16 September 2015

DOMINGOS DELLAMONICA Jr ,
YOSHIHARU KOHAYAKAWA ,
SANG JUNE LEE ,
VOJTĚCH RÖDL  and
WOJCIECH SAMOTIJ
DOMINGOS DELLAMONICA Jr
Affiliation:
Department of Mathematics and Computer Science, Emory University, Atlanta, GA 30322, USA (e-mail: domingos.junior@gmail.com, rodl@mathcs.emory.edu)
YOSHIHARU KOHAYAKAWA
Affiliation:
Department of Mathematics and Computer Science, Emory University, Atlanta, GA 30322, USA (e-mail: domingos.junior@gmail.com, rodl@mathcs.emory.edu) Instituto de Matemática e Estatística, Universidade de São Paulo, Rua do Matão 1010, 05508-090 São Paulo, Brazil (e-mail: yoshi@ime.usp.br)
SANG JUNE LEE
Affiliation:
Department of Mathematics, Duksung Women's University, Seoul 132-714, South Korea (e-mail: sanglee242@duksung.ac.kr, sjlee242@gmail.com)
VOJTĚCH RÖDL
Affiliation:
Department of Mathematics and Computer Science, Emory University, Atlanta, GA 30322, USA (e-mail: domingos.junior@gmail.com, rodl@mathcs.emory.edu)
WOJCIECH SAMOTIJ
Affiliation:
School of Mathematical Sciences, Tel Aviv University, Tel Aviv 69978, Israel and Trinity College, Cambridge CB2 1TQ, UK (e-mail: samotij@post.tau.ac.il)
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.

A set A of positive integers is a Bh-set if all the sums of the form a1 + . . . + ah, with a1,. . .,ah ∈ A and a1 ⩽ . . . ⩽ ah, are distinct. We provide asymptotic bounds for the number of Bh-sets of a given cardinality contained in the interval [n] = {1,. . .,n}. As a consequence of our results, we address a problem of Cameron and Erdős (1990) in the context of Bh-sets. We also use these results to estimate the maximum size of a Bh-sets contained in a typical (random) subset of [n] with a given cardinality.

MSC classification

Primary: 11B75: Other combinatorial number theory 05A16: Asymptotic enumeration
Secondary: 05D40: Probabilistic methods 11B83: Special sequences and polynomials
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 25 , Issue 1: Oberwolfach Special Issue Part 2 , January 2016 , pp. 108 - 129
Copyright
Copyright © Cambridge University Press 2015 

References

[1]Alon, N., Balogh, J., Morris, R. and Samotij, W. (2014) Counting sum-free sets in Abelian groups. Israel J. Math. 199 309–344.CrossRefGoogle Scholar
[2]Bose, R. C. and Chowla, S. (1962/1963) Theorems in the additive theory of numbers. Comment. Math. Helv. 37 141–147.CrossRefGoogle Scholar
[3]Cameron, P. J. and Erdős, P. (1990) On the number of sets of integers with various properties. In Number Theory (Banff 1988), de Gruyter, pp. 61–79.Google Scholar
[4]Chen, S. (1994) On the size of finite Sidon sequences. Proc. Amer. Math. Soc. 121 353–356.CrossRefGoogle Scholar
[5]Chowla, S. (1944) Solution of a problem of Erdős and Turán in additive-number theory. Proc. Nat. Acad. Sci. India. Sect. A 14 1–2.Google Scholar
[6]Cilleruelo, J. (2001) New upper bounds for finite Bh sequences. Adv. Math. 159 1–17.CrossRefGoogle Scholar
[7]Conlon, D. and Gowers, W. T. (2010) Combinatorial theorems in sparse random sets. Submitted.Google Scholar
[8]D'yachkov, A. G. and Rykov, V. V. (1984) Bs-sequences. Mat. Zametki 36 593–601.Google Scholar
[9]Erdős, P. (1944) On a problem of Sidon in additive number theory and on some related problems: Addendum. J. London Math. Soc. 19 208.CrossRefGoogle Scholar
[10]Erdős, P. and Turán, P. (1941) On a problem of Sidon in additive number theory, and on some related problems. J. London Math. Soc. 16 212–215.CrossRefGoogle Scholar
[11]Green, B. (2001) The number of squares and Bh[g] sets. Acta Arith. 100 365–390.CrossRefGoogle Scholar
[12]Halberstam, H. and Roth, K. F. (1983) Sequences, second edition, Springer.CrossRefGoogle Scholar
[13]Hardy, G. H., Littlewood, J. E. and Polya, G. (1934) Inequalities, Cambridge University Press.Google Scholar
[14]Janson, S., Łuczak, T. and Ruciński, A. (2000) Random Graphs, Wiley-Interscience.CrossRefGoogle Scholar
[15]Jia, X. D. (1993) On finite Sidon sequences. J. Number Theory 44 84–92.CrossRefGoogle Scholar
[16]Kleitman, D. J. and Wilson, D. B. (1996) On the number of graphs which lack small cycles. Unpublished Manuscript.Google Scholar
[17]Kleitman, D. J. and Winston, K. J. (1982) On the number of graphs without 4-cycles. Discrete Math. 41 167–172.CrossRefGoogle Scholar
[18]Kohayakawa, Y., Lee, S. J., Rödl, V. and Samotij, W. (2015) The number of Sidon sets and the maximum size of Sidon sets contained in a sparse random set of integers. Random Struct. Alg. 46 1–25.CrossRefGoogle Scholar
[19]Kohayakawa, Y., Lee, S. and Rödl, V. (2011) The maximum size of a Sidon set contained in a sparse random set of integers. In Proc. Twenty-Second Annual ACM–SIAM Symposium on Discrete Algorithms (Philadelphia, PA), SIAM, pp. 159–171.CrossRefGoogle Scholar
[20]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
[21]Kolountzakis, M. N. (1996) The density of Bh[g] sequences and the minimum of dense cosine sums. J. Number Theory 56 4–11.CrossRefGoogle Scholar
[22]Krückeberg, F. (1961) B 2-Folgen und verwandte Zahlenfolgen. J. Reine Angew. Math. 206 53–60.CrossRefGoogle Scholar
[23]Lee, S. J. On Sidon sets in a random set of vectors. J. Korean Math. Soc., to appear.Google Scholar
[24]Lindström, B. (1969) A remark on B 4-sequences. J. Combin. Theory 7 276–277.CrossRefGoogle Scholar
[25]O'Bryant, K. (2004) A complete annotated bibliography of work related to Sidon sequences. Electron. J. Combin. Dynamic Surveys 11 (electronic).CrossRefGoogle Scholar
[26]Roth, K. F. (1953) On certain sets of integers. J. London Math. Soc. 28 104–109.CrossRefGoogle Scholar
[27]Saxton, D. and Thomason, A. (2015) Hypergraph containers, Invent. Math., 201 925–992CrossRefGoogle Scholar
[28]Schacht, M. Extremal results for random discrete structures. Submitted.Google Scholar
[29]Shparlinskii, I. E. (1986) On Bs-sequences. In Combinatorial Analysis, no. 7 (Russian), Moscow State University, pp. 42–45.Google Scholar
[30]Singer, J. (1938) A theorem in finite projective geometry and some applications to number theory. Trans. Amer. Math. Soc. 43 377–385.CrossRefGoogle Scholar
[31]Szemerédi, E. (1975) On sets of integers containing no k elements in arithmetic progression. Acta Arith. 27 199–245.CrossRefGoogle Scholar