The number of Sidon sets and the maximum size of Sidon sets contained in a sparse random set of integers |
| |
Authors: | Yoshiharu Kohayakawa Sang June Lee Vojtěch Rödl Wojciech Samotij |
| |
Institution: | 1. Instituto de Matemática e Estatística, Universidade de S?o Paulo, S?o Paulo, Brazil;2. Department of Mathematics and Computer Science, Emory University, Atlanta, GeorgiaPartially supported by CNPq (Proc. 308509/2007‐2 and Proc. 484154/2010‐9);3. NUMEC/USP (Project MaCLinC/USP);4. NSF (DMS 1102086).;5. Department of Mathematical Sciences, Korea Advanced Institute of Science and Technology (KAIST), Daejeon, South KoreaSupported by the Korea Institute for Advanced Study (KIAS) grant and by the National Research Foundation of Korea (NRF) grant (No. 20120000798) funded by the Korea government (MEST).;6. Department of Mathematics and Computer Science, Emory University, Atlanta, GeorgiaSupported by NSF (DMS 0800070 and DMS 1102086).;7. School of Mathematical Sciences, Tel Aviv University, Tel Aviv, Israel;8. Trinity College, Cambridge, UKPartially supported by ERC Advanced Grant DMMCA and a Trinity College JRF. |
| |
Abstract: | A set A of non‐negative integers is called a Sidon set if all the sums , with and a1, , are distinct. A well‐known problem on Sidon sets is the determination of the maximum possible size F(n) of a Sidon subset of . Results of Chowla, Erd?s, Singer and Turán from the 1940s give that . We study Sidon subsets of sparse random sets of integers, replacing the ‘dense environment’ by a sparse, random subset R of , and ask how large a subset can be, if we require that S should be a Sidon set. Let be a random subset of of cardinality , with all the subsets of equiprobable. We investigate the random variable , where the maximum is taken over all Sidon subsets , and obtain quite precise information on for the whole range of m, as illustrated by the following abridged version of our results. Let be a fixed constant and suppose . We show that there is a constant such that, almost surely, we have . As it turns out, the function 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 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 |
| |
Keywords: | Sidon sets random sets of integers probabilistic extremal problems additive combinatorics |
|
|