99-23   Berichtsreihe des Mathematischen Seminars der Universität Kiel

Andreas Baltz, Tomasz Schoen, Anand Srivastav:

Probabilistic Construction of Small Strongly Sum-Free Sets via Large Sidon Sets

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 Pn(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 Pn(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 subset of [2n,4n)}<=cn^(3/4). We improve this bound to c(n ln(n))^(2/3). Turning to a problem of Erdös, suppose that S is an element of Pn(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 group,S in Pn(G)}<=c(ln(n))^2. Our approach relies on the existence of large Sidon sets.

Mathematics Subject Classification (1991): Klassifikation

Bibliographical note: Colloquium Mathematicum 86, No.2, 171-176 (2000)

Keywords: Schlagworte

Mail an Jens Burmeister
[Thu Feb 19 18:56:35 2009]
Impressum