Department of Mathematics and Computer Science, Emory University, Atlanta, Georgia, USA

A set A of integers is a *Sidon set* if all the sums a_{1}+a_{2}, with a_{1}≤a_{2} and a_{1}, a_{2}∈A, are distinct. In the 1940s, Chowla, Erdős and Turán showed that the maximum possible size of a Sidon set contained in [n]={0,1,…,n-1} is √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| : S⊆[n]_{m} Sidon}. An abridged version of our results states as follows. Fix a constant 0≤a≤1 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ödl.

Tags: 이상준