MATH Seminar

Title: The maximum size of a Sidon set contained in a sparse random set of integers
Seminar: Combinatorics
Speaker: Sangjune Lee of Emory University
Contact: Dwight Duffus, dwight@mathcs.emory.edu
Date: 2011-04-08 at 4:00PM
Venue: W306
Download Flyer
Abstract: A set $A$ of integers is a \textit{Sidon set} if all the sums~$a_1+a_2$, with~$a_1\leq a_2$ and~$a_1$,~$a_2\in A$, are distinct. In the 1940s, Chowla, Erd\H{o}s and Tur\'an showed that the maximum possible size of a Sidon set contained in $[n]=\{0,1,\dots,n-1\}$ is $\sqrt{n}(1+o(1))$. We study Sidon sets contained in sparse random sets of integers, replacing the `dense environment'~$[n]$ by a sparse, random subset~$R$ of~$[n]$.\\ \\ Let~$R=[n]_m$ be a uniformly chosen, random $m$-element subset of~$[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$. Then there is a constant $b=b(a)$ for which~$F([n]_m)=n^{b+o(1)}$ almost surely. The function~$b=b(a)$ is a continuous, piecewise linear function of~$a$, not differentiable at two points:~$a=1/3$ and~$a=2/3$; between those two points, the function~$b=b(a)$ is constant. \\ \\ This is joint work with Yoshiharu Kohayakawa and Vojtech R\"odl.