Premium
The number of Sidon sets and the maximum size of Sidon sets contained in a sparse random set of integers
Author(s) -
Kohayakawa Yoshiharu,
Lee Sang June,
Rödl Vojtěch,
Samotij Wojciech
Publication year - 2015
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20496
Subject(s) - mathematics , cardinality (data modeling) , combinatorics , constant (computer programming) , function (biology) , discrete mathematics , set (abstract data type) , piecewise , piecewise linear function , computer science , mathematical analysis , evolutionary biology , biology , data mining , programming language , geometry
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