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

• Autorzy: Andreas Schoen , Tomasz Srivastav , Anand Baltz
• Języki publikacji: EN

Abstrakty

EN

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.

• Wydawca: Institute of Mathematics Polish Academy of Sciences
• Czasopismo: Colloquium Mathematicum
• Rocznik: 2000
• Tom: 86
• Numer: 2
• Strony: 171-176

Daty

wydano

2000

otrzymano

1999-05-04

poprawiono

1999-12-01

Twórcy

autor

Andreas Schoen

• Mathematisches Seminar, Christian-Albrechts-Universität zu Kiel, Ludewig-Meyn-Str. 4, D-24098 Kiel, Germany

autor

Tomasz Srivastav

• Mathematisches Seminar, Christian-Albrechts-Universität zu Kiel, Ludewig-Meyn-Str. 4, D-24098 Kiel, Germany

autor

Anand Baltz

• Mathematisches Seminar, Christian-Albrechts-Universität zu Kiel, Ludewig-Meyn-Str. 4, D-24098 Kiel, Germany

Bibliografia

• [1] S. L. G. Choi, On a combinatorial problem in number theory, Proc. London Math. Soc. (3) 23 (1971), 629-642.
• [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.
• [5] T. Łuczak and T. Schoen, On strongly sum-free subsets of abelian groups, Colloq. Math. 71 (1996), 149-151.