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

Colloquium Mathematicae (2000)

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

top

## Abstract

top
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}\left(G\right)$ 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}\left(G\right)$ 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\left(n\right):=min|S|+f\left(S\right)|S\subseteq \left[2n,4n\right)=O{n}^{3/4}\right)$. We improve this bound to $O{\left(nln\left(n\right)\right)}^{2/3}\right)$. Turning to a problem of Erdős, suppose that S is an element of ${P}_{n}\left(G\right)$, 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\left(n\right):=minh\left(S\right)|Gagroup,S\in {P}_{n}\left(G\right)=O{\left(ln\left(n\right)\right)}^{2}\right)$. Our approach relies on the existence of large Sidon sets.

## How to cite

top

Schoen, 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. [1] S. L. G. Choi, On a combinatorial problem in number theory, Proc. London Math. Soc. (3) 23 (1971), 629-642. Zbl0225.10058
2. [2] P. Erdős, Extremal problems in number theory, in: Proc. Sympos. Pure Math. 8, Amer. Math. Soc., Providence, RI, 1965, 181-189.
3. [3] R. F. Guy, Unsolved Problems in Number Theory, Springer, New York, 1994, Problem C14, 128-129.
4. [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. [5] T. Łuczak and T. Schoen, On strongly sum-free subsets of abelian groups, Colloq. Math. 71 (1996), 149-151. Zbl0856.05097

## NotesEmbed?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.