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

Schoen, Andreas; Srivastav, Tomasz; Baltz, Anand

Schoen, Andreas ; Srivastav, Tomasz ; Baltz, Anand

Colloquium Mathematicae, Tome 84/85 (2000), p. 171-176 / Harvested from The Polish Digital Mathematics Library

Résumé

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) : = m i n | S | + f (S) | S \subseteq [2 n, 4 n) = O n^{3 / 4})$ . We improve this bound to $O {(n l n (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) : = m i n h (S) | G a g r o u p, S \in P_{n} (G) = O {(l n (n))}^{2})$ . Our approach relies on the existence of large Sidon sets.

Publié le : 2000-01-01

Zbl 0961.11003

EUDML-ID : urn:eudml:doc:210847

@article{bwmeta1.element.bwnjournal-article-cmv86i2p171bwm,
     author = {Andreas Schoen and Tomasz Srivastav and Anand Baltz},
     title = {Probabilistic construction of small strongly sum-free sets via large Sidon sets},
     journal = {Colloquium Mathematicae},
     volume = {84/85},
     year = {2000},
     pages = {171-176},
     zbl = {0961.11003},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-cmv86i2p171bwm}
}

Schoen, Andreas; Srivastav, Tomasz; Baltz, Anand. Probabilistic construction of small strongly sum-free sets via large Sidon sets. Colloquium Mathematicae, Tome 84/85 (2000) pp. 171-176. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-cmv86i2p171bwm/

Bibliographie

[000] [1] S. L. G. Choi, On a combinatorial problem in number theory, Proc. London Math. Soc. (3) 23 (1971), 629-642. | Zbl 0225.10058

[001] [2] P. Erdős, Extremal problems in number theory, in: Proc. Sympos. Pure Math. 8, Amer. Math. Soc., Providence, RI, 1965, 181-189.

[002] [3] R. F. Guy, Unsolved Problems in Number Theory, Springer, New York, 1994, Problem C14, 128-129.

[003] [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. | Zbl 0303.10058

[004] [5] T. Łuczak and T. Schoen, On strongly sum-free subsets of abelian groups, Colloq. Math. 71 (1996), 149-151. | Zbl 0856.05097