INFINITE SIDON SETS CONTAINED IN SPARSE RANDOM SETS OF INTEGERS

Autor(es)

Kohayakawa, Yoshiharu ^[1] ; Lee, Sang June ^[2] ; Moreira, Carlos Gustavo ^[3] ; Rodl, Vojtech ^[4]

Afiliação do(s) autor(es)

^[1] Univ Sao Paulo, Inst Matemat & Estat, Rua Matao 1010, BR-05508090 Sao Paulo - Brazil

^[2] Duksung Womens Univ, Dept Math, Seoul 01369 - South Korea

^[3] IMPA, Estr Dona Castorina 110, BR-22460320 Rio De Janeiro - Brazil

^[4] Emory Univ, Dept Math & Comp Sci, Atlanta, GA 30322 - USA

• Tipo de documento: Artigo Científico
• Fonte: SIAM JOURNAL ON DISCRETE MATHEMATICS; v. 32, n. 1, p. 410-449, 2018.
• Citações Web of Science: 0

Resumo

A set S of natural numbers is a Sidon set if all the sums s(1) + s(2) with s(1), s(2) epsilon S and s(1) <= s(2) are distinct. Let constants alpha > 0 and 0 < delta < 1 be fixed, and let p(m) = min[1, alpha m (1 vertical bar delta)] for all positive integers m. Generate a random set R subset of N by adding m to R with probability p(m), independently for each m. We investigate how dense a Sidon set S contained in R can be. Our results show that the answer is qualitatively very different in at least three ranges of delta. We prove quite accurate results for the range 0 < delta <= 2/3, but only obtain partial results for the range 2/3 < delta <= 1. (AU)

• Processo FAPESP: 13/03447-6 - Estruturas combinatórias, otimização e algoritmos em Teoria da Computação
• Beneficiário: Carlos Eduardo Ferreira
• Modalidade de apoio: Auxílio à Pesquisa - Temático
• Processo FAPESP: 13/07699-0 - Centro de Pesquisa, Inovação e Difusão em Neuromatemática - NeuroMat
• Beneficiário: Oswaldo Baffa Filho
• Modalidade de apoio: Auxílio à Pesquisa - Centros de Pesquisa, Inovação e Difusão - CEPIDs