The number of Sidon sets and the maximum size of Sidon sets contained in a sparse random set of integers1. Issue 1 (3rd April 2013) - Kohayakawa, Yoshiharu; Lee, Sang June; Rödl, Vojtěch; Samotij, Wojciech
Abstract A set A of non‐negative integers is called a Sidon set if all the sums <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh2d2rbbx4" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />a1+a2</alternatives>, with <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh2d2rbc2v" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />a1≤a2</alternatives> and a1, <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh2d2rbbqt" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />a2∈A</alternatives>, are distinct. A well‐known problem on Sidon sets is the determination of the maximum possible size F(n) of a Sidon subset of <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh2d2rbbwk" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />[n]=0, 1, …, n−1</alternatives>. Results of Chowla, Erdős, Singer and Turán from the 1940s give that <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh2d2rbcrw" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />F(n)=(1+o(1))n</alternatives>. We study Sidon subsets of sparse random sets of integers, replacing the 'dense environment' <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh2d2rbck4" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />[n]</alternatives> by a sparse, random subset R of <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh2d2rbcjk" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />[n]</alternatives>, and ask how large a subset <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh2d2rbcct" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />S⊂R</alternatives> can be, if we require that S should be a Sidon set. Let <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh2d2rbcw3" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />R=[n]m</alternatives> be a random subset of <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh2d2rbd1t" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />[n]</alternatives> of cardinality <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh2d2rbd3x" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />m=m(n)</alternatives>, with all the <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh2d2rbd51" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />(nm)</alternatives> subsets of <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh2d2rbd97" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />[n]</alternatives> equiprobable. We investigate the random variable <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh2d2rbddw" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />F([n]m)=max|S|</alternatives>, where the maximum is taken over all Sidon subsets <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh2d2rbdff" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />S⊂[n]m</alternatives>, and obtain quite precise information on <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh2d2rbdzq" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />F([n]m)</alternatives> for the whole range of m, as illustrated by the following abridged version of our results. Let <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh2d2rbdsz" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />0≤a≤1</alternatives> be a fixed constant and suppose <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh2d2rbf63" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />m=m(n)=(1+o(1))na</alternatives>. We show that there is a constant <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh2d2rbf1b" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />b=b(a)</alternatives> such that, almost surely, we have <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh2d2rbg1v" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />F([n]m)=nb+o(1)</alternatives>. As it turns out, the function <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh2d2rbfrx" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />b=b(a)</alternatives> 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 <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh2d2rbft1" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />b=b(a)</alternatives> 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