KAIST Discrete Math Seminar

Let N be the set of natural numbers. A set A⊂N is called a Sidon set if the sums a₁+a₂, with a₁,a₂∈S and a₁≤a₂, are distinct, or equivalently, if
|(x+w)−(y+z)|≥1
for every x,y,z,w∈S with x<y≤z<w. We define strong Sidon sets as follows:

For a constant α with 0≤α<1, a set S⊂N is called an α-strong Sidon set if
|(x+w)−(y+z)|≥w^α
for every x,y,z,w∈S with x<y≤z<w.

The motivation of strong Sidon sets is that a strong Sidon set generates many Sidon sets by altering each element a bit. This infers that a dense strong Sidon set will guarantee a dense Sidon set contained in a sparse random subset of N.

In this talk, we are interested in how dense a strong Sidon set can be. This is joint work with Yoshiharu Kohayakawa, Carlos Gustavo Moreira and Vojtěch Rödl.