|
|
|
| |
|
|
|
 |
|
|
| KAIST Discrete Math Seminar |
|
|
|
|
|
|
|
 |
Title |
|
| |
Speaker |
Lee, Sangjune (Emory University) |
|
| |
Date |
2011-06-09 |
|
| |
Host |
|
|
| |
Place |
KAIST |
|
| |
File |
 |
|
|
|
| |
 Abstract : 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. |
|
|
 |
|
|
|
.jpg)
