Abstract:
A set~$A$ of non-negative integers is called 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. A well-known problem on Sidon sets is the
determination of the maximum possible size~$F(n)$ of a Sidon subset
of $[n]=\{0,1,\dots,n-1\}$. Results of Chowla, Erd\H{o}s, Singer and
Tur\'an from the 1940s give that $F(n)=(1+o(1))\sqrt{n}$. We study
Sidon subsets of sparse random sets of integers, replacing the
`dense environment'~$[n]$ by a sparse, random subset~$R$ of~$[n]$,
and ask how large a subset~$S\subset R$ can be, if we require
that~$S$ should be a Sidon set.
Let~$R=[n]_m$ be a random subset of~$[n]$ of cardinality~$m=m(n)$,
with all the~${n\choose m}$ subsets of~$[n]$ equiprobable. We
investigate the random variable~$F([n]_m)=\max|S|$, where the
maximum is taken over all Sidon subsets~$S\subset[n]_m$, and obtain
quite precise information on~$F([n]_m)$ for the whole range of~$m$,
as illustrated by the following abridged version of our results.
Let~$0\leq a\leq1$ be a fixed constant and
suppose~$m=m(n)=(1+o(1))n^a$. We show that there is a constant
$b=b(a)$ such that, almost surely, we have~$F([n]_m)=n^{b+o(1)}$.
As it turns out, the function~$b=b(a)$ is a continuous, piecewise
linear function of~$a$ that is non-differentiable at two `critical'
points:~$a=1/3$ and~$a=2/3$. Somewhat surprisingly, between those
two points, the function~$b=b(a)$ is constant.
Our approach is based on estimating the number of Sidon sets of a
given cardinality contained in~$[n]$. Our estimates also directly
address a problem raised by Cameron and Erd\H os [\emph{On the
number of sets of integers with various properties}, Number theory
({B}anff, {AB}, 1988), de Gruyter, Berlin, 1990, pp.~61--79].
Published Papers
Home > Activities > Outputs > Published Papers
Title 
1365646147_0.930967.pdf