============================================================
   Seminário de Teoria da Computação e Combinatória (TCC)

============================================================

Título:      The maximum size of a Sidon subset of a random 
             set of integers in [n]

            
Palestrante: Sangjune Lee
             Emory University

Hora e Data: 14h00, sexta-feira, 16 de julho de 2010

Local:       auditório do NUMEC

Resumo:

A set  $A$ of integers is  called a \emph{Sidon  set} if all
sums  $a_1+a_2$   ($a_1\leq  a_2$,  $a_1,   a_2\in  A$)  are
distinct.  A well-studied problem on Sidon sets asks for the
determination of  the maximum size $F(n)$ of  a Sidon subset
of  $[n]$.  It  follows from  works by  Erd\H{o}s  and Turán
(1941) and Chowla (1944) that $F(n)=(1+o(1))\sqrt n$.

In this talk, we will discuss the related question regarding
the random  subsets $[n]_p$ of $[n]$,  obtained by including
each  element in $[n]$  independently with  probability $p$.
Let $F([n]_p)$ denote the maximum  size of a Sidon subset of
the random set $[n]_p$.  We  will give almost sure lower and
upper bounds on $F([n]_p)$,  nearly determining the order of
magnitude   of   $F([n]_p)$   for   all   $p=p(n)$.    Quite
surprisingly,  $F([n]_p)$  undergoes   a  sudden  change  of
behaviour at two critical points: when $p$ is of order about
$n^{-2/3}$ and when $p$ is of order about $n^{-1/3}$.

This is joint work with Y. Kohayakawa and V. Rödl.