# Probabilistic construction of small strongly sum-free sets via large Sidon sets

Andreas Schoen; Tomasz Srivastav; Anand Baltz

Colloquium Mathematicae (2000)

- Volume: 86, Issue: 2, page 171-176
- ISSN: 0010-1354

## Access Full Article

top## Abstract

top## How to cite

topSchoen, Andreas, Srivastav, Tomasz, and Baltz, Anand. "Probabilistic construction of small strongly sum-free sets via large Sidon sets." Colloquium Mathematicae 86.2 (2000): 171-176. <http://eudml.org/doc/210847>.

@article{Schoen2000,

abstract = {We give simple randomized algorithms leading to new upper bounds for combinatorial problems of Choi and Erdős: For an arbitrary additive group G let $P_n(G)$ denote the set of all subsets S of G with n elements having the property that 0 is not in S+S. Call a subset A of G admissible with respect to a set S from $P_n(G)$ if the sum of each pair of distinct elements of A lies outside S. Suppose first that S is a subset of the positive integers in the interval [2n,4n). Denote by f(S) the number of elements in a maximum subset of [n,2n) admissible with respect to S. Choi showed that $f(n):=min\{|S|+f(S)| S ⊆ [2n,4n)\} = On^\{3/4\})$. We improve this bound to $O(n ln(n))^\{2/3\})$. Turning to a problem of Erdős, suppose that S is an element of $P_n(G)$, where G is an arbitrary additive group, and denote by h(S) the maximum cardinality of a subset A of S admissible with respect to S. We show $h(n):=min\{h(S) | G a group, S ∈ P_n(G)\}=O(ln(n))^2)$. Our approach relies on the existence of large Sidon sets.},

author = {Schoen, Andreas, Srivastav, Tomasz, Baltz, Anand},

journal = {Colloquium Mathematicae},

language = {eng},

number = {2},

pages = {171-176},

title = {Probabilistic construction of small strongly sum-free sets via large Sidon sets},

url = {http://eudml.org/doc/210847},

volume = {86},

year = {2000},

}

TY - JOUR

AU - Schoen, Andreas

AU - Srivastav, Tomasz

AU - Baltz, Anand

TI - Probabilistic construction of small strongly sum-free sets via large Sidon sets

JO - Colloquium Mathematicae

PY - 2000

VL - 86

IS - 2

SP - 171

EP - 176

AB - We give simple randomized algorithms leading to new upper bounds for combinatorial problems of Choi and Erdős: For an arbitrary additive group G let $P_n(G)$ denote the set of all subsets S of G with n elements having the property that 0 is not in S+S. Call a subset A of G admissible with respect to a set S from $P_n(G)$ if the sum of each pair of distinct elements of A lies outside S. Suppose first that S is a subset of the positive integers in the interval [2n,4n). Denote by f(S) the number of elements in a maximum subset of [n,2n) admissible with respect to S. Choi showed that $f(n):=min{|S|+f(S)| S ⊆ [2n,4n)} = On^{3/4})$. We improve this bound to $O(n ln(n))^{2/3})$. Turning to a problem of Erdős, suppose that S is an element of $P_n(G)$, where G is an arbitrary additive group, and denote by h(S) the maximum cardinality of a subset A of S admissible with respect to S. We show $h(n):=min{h(S) | G a group, S ∈ P_n(G)}=O(ln(n))^2)$. Our approach relies on the existence of large Sidon sets.

LA - eng

UR - http://eudml.org/doc/210847

ER -

## References

top- [1] S. L. G. Choi, On a combinatorial problem in number theory, Proc. London Math. Soc. (3) 23 (1971), 629-642. Zbl0225.10058
- [2] P. Erdős, Extremal problems in number theory, in: Proc. Sympos. Pure Math. 8, Amer. Math. Soc., Providence, RI, 1965, 181-189.
- [3] R. F. Guy, Unsolved Problems in Number Theory, Springer, New York, 1994, Problem C14, 128-129.
- [4] J. Komlós, M. Sulyok and E. Szemerédi, Linear problems in combinatorial number theory, Acta Math. Acad. Sci. Hungar. 26 (1975), 113-121. Zbl0303.10058
- [5] T. Łuczak and T. Schoen, On strongly sum-free subsets of abelian groups, Colloq. Math. 71 (1996), 149-151. Zbl0856.05097

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.