The maximum size of a Sidon set contained in a sparse random set of integers

Combinatorics Seminar
Friday, April 1, 2011 - 15:05
1 hour (actually 50 minutes)
Skiles 006
Emory University
A set~$A$ of integers is a \textit{Sidon set} if all thesums~$a_1+a_2$, with~$a_1\leq a_2$ and~$a_1$,~$a_2\in A$, aredistinct.  In the 1940s, Chowla, Erd\H{o}s and Tur\'an determinedasymptotically the maximum possible size of a Sidon set contained in$[n]=\{0,1,\dots,n-1\}$.  We study Sidon sets contained in sparserandom sets of integers, replacing the `dense environment'~$[n]$ by asparse, random subset~$R$ of~$[n]$.Let~$R=[n]_m$ be a uniformly chosen, random $m$-element subsetof~$[n]$.  Let~$F([n]_m)=\max\{|S|\colon S\subset[n]_m\hbox{  Sidon}\}$.  An abridged version of our results states as follows.Fix a constant~$0\leq a\leq1$ and suppose~$m=m(n)=(1+o(1))n^a$.  Thenthere is a constant $b=b(a)$ for which~$F([n]_m)=n^{b+o(1)}$ almostsurely.  The function~$b=b(a)$ is a continuous, piecewise linearfunction of~$a$, not differentiable at two points:~$a=1/3$and~$a=2/3$; between those two points, the function~$b=b(a)$ isconstant.