- Tytuł:
- Probabilistic construction of small strongly sum-free sets via large Sidon sets
- Autorzy:
-
Schoen, Andreas
Srivastav, Tomasz
Baltz, Anand - Powiązania:
- https://bibliotekanauki.pl/articles/965829.pdf
- Data publikacji:
- 2000
- Wydawca:
- Polska Akademia Nauk. Instytut Matematyczny PAN
- Opis:
- 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.
- Źródło:
-
Colloquium Mathematicum; 2000, 86, 2; 171-176
0010-1354 - Pojawia się w:
- Colloquium Mathematicum
- Dostawca treści:
- Biblioteka Nauki
Artykuł