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

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 -