The number of Sidon sets and the maximum size of Sidon sets contained in a sparse random set of integers

A set A of non‐negative integers is called a Sidon set if all the sumsa 1 + a 2 , witha 1 ≤ a 2and a 1 ,a 2 ∈ 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 , … , n − 1 } . Results of Chowla, Erdős, Singer and Turán from the 1940s give that F ( n ) = ( 1 + o ( 1 ) ) 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 ⊂ R can be, if we require that S should be a Sidon set. Let R = [ n ] mbe a random subset of [ n ] of cardinality m = m ( n ) , with all the(nm)subsets of [ n ] equiprobable. We investigate the random variable F ( [ n ] m ) = max | S | , where the maximum is taken over all Sidon subsets S ⊂ [ 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 ≤ a ≤ 1 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ős (On the number of sets of integers with various properties, Number theory (Banff, AB, 1988), de Gruyter, Berlin, 1990, pp. 61–79). © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 46, 1–25, 2015