A set $S$ of natural numbers is a Sidon set if all the sums $s_1+s_2$ with $s_1$, $s_2\in S$ and $s_1\leq s_2$ are distinct. Let constants $\alpha>0$ and $0<\delta<1$ be fixed, and let $p_m=\min\{1,\alpha m^{-1+\delta}\}$ for all positive integers $m$. Generate a random set $R\subset {\mathbb N}$ by adding $m$ to $R$ with probability $p_m$, independently for each $m$. We investigate how dense a Sidon set $S$ contained in $R$ can be. Our results show that the answer is qualitatively very different in at least three ranges of $\delta$. We prove quite accurate results for the range $0<\delta\leq2/3$, but only obtain partial results for the range $2/3<\delta\leq1$.

For a family $\mathcal{F}$ of graphs, a graph $G$ is called $\mathcal{F}$-universal if $G$ contains every graph in $\mathcal{F}$ as a subgraph. Let $\mathcal{F}_n(d)$ be the family of all graphs on $n$ vertices with maximum degree at most $d$. Dellamonica, Kohayakawa, Rödl, and Ruciński [An improved upper bound on the density of universal random graphs, Random Structures & Algorithms, doi:10.1002/rsa.20545] showed that, for $d\geq 3$, the random graph $G(n,p)$ is $\mathcal{F}_n(d)$-universal with high probability provided $p\geq C(\frac{\log n}{n})^{1/d}$ for a sufficiently large constant $C=C(d)$. In this paper we prove the missing part of the result, that is, the random graph $G(n,p)$ is $\mathcal{F}_n(2)$-universal with high probability provided $p\geq C(\frac{\log n}{n})^{1/2}$ for a sufficiently large constant $C$.

A set A of non-negative integers is called a Sidon set if all the sums a1 + a2, with a1 ≤ a2 and a1, a2 ∊ A, are distinct. One of the best studied problems on Sidon sets is the determination of the maximum possible size F(n) of a Sidon subset of [n] = {0, 1, …, n − 1}. Thanks to results of Chowla, Erdős and Turán from the 1940s, it is known that F(n) = (1 + o(1))√n. In this paper 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]m be a random subset of [n] of cardinality m = m(n), with all the 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. An abridged version of our results states as follows. Let 0 < a < 1 be a fixed constant and suppose m = m(n) = (1 + o(1))na. We show that there is a constant b = b(a) such that, almost surely, we have F([n]m) = nb+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 points: a = 1/3 and a = 2/3. Somewhat surprisingly, between those two points, the function b = b(a) is constant.