Given graphs G, H1 and H2, let G→mr(H1, H2) denote the property that in every edge-colouring of G there is a monochromatic copy of H1 or a rainbow copy of H2. The constrained Ramsey number, defined as the minimum n such that Kn→mr(H1, H2), exists if and only if H1 is a star or H2 is a forest. We determine the threshold for the property G(n,p) →mr(H1, H2) when H2 is a forest.

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$.

There has been great interest in deciding whether a combinatorial structure satisfies some property, or in estimating the value of some numerical function associated with this combinatorial structure, by considering only a randomly chosen substructure of sufficiently large, but constant size. These problems are called property testing and parameter testing, where a property or parameter is said to be testable if it can be estimated accurately in this way. The algorithmic appeal is evident, as, conditional on sampling, this leads to reliable constant-time randomized estimators. Our paper addresses property testing and parameter testing for permutations in a subpermutation perspective; more precisely, we investigate permutation properties and parameters that can be well-approximated based on randomly chosen subpermutations of much smaller size. In this context, we give a permutation counterpart of a famous result by Alon and Shapira [6] stating that every hereditary graph property is testable. Moreover, we develop a theory of convergence of permutation sequences, which is used to characterize testable permutation parameters along the lines of the work of Borgs et al. [12] in the case of graphs. This theory is interesting for its own sake, as it describes the closure of the set of all permutations as a special class of Lebesgue measurable functions in [0, 1]2, which in turn may be used to define a new model of random permutations.