PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2000 | 86 | 2 | 171-176
Tytuł artykułu

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

Treść / Zawartość
Warianty tytułu
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.
Słowa kluczowe
Rocznik
Tom
86
Numer
2
Strony
171-176
Opis fizyczny
Daty
wydano
2000
otrzymano
1999-05-04
poprawiono
1999-12-01
Twórcy
  • Mathematisches Seminar, Christian-Albrechts-Universität zu Kiel, Ludewig-Meyn-Str. 4, D-24098 Kiel, Germany
  • Mathematisches Seminar, Christian-Albrechts-Universität zu Kiel, Ludewig-Meyn-Str. 4, D-24098 Kiel, Germany
autor
  • 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.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-cmv86i2p171bwm
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.