The number of Sidon sets and an application to an extremal problem for random sets of integers

A set of integers is a Sidon set if the pairwise sums of its elements are all distinct. We discuss the number of Sidon sets contained in $[n]=\{1,2,\ldots,n\}$.

As an application, we investigate random subsets $R$ of $[n]$ of a given cardinality $m=m(n)$ and study $F(R)$, the typical maximal cardinality of a Sidon set contained in $R$. The behavior of $F(R)$ as $m=m(n)$ varies is somewhat unexpected, presenting two points of "phase transition." We shall also briefly discuss the case in which the random set $R$ is an infinite random subset of the set of natural numbers, according to a natural model; that is, we shall discuss infinite Sidon sets contained in certain infinite random sets of integers. Finally, we shall mention extensions to $B_h$-sets.

Joint work with D. Dellamonica Jr., S. J. Lee, C. G. Moreira, V. Rödl, and W. Samotij.

Yoshiharu Kohayakawa