Preprint C191/2015
Sparse random subsets of combinatorial objects
Mauricio de Lemos Rodrigues Collares Neto
Keywords: sparse random problems | probabilistic combinatorics | hypergraph container method | thresholds

This thesis is concerned with the extremal properties and typical structure of sparse random combinatorial objects.

The first chapter, which is joint work with Morris, deals with a sparse random variant of a generalisation of Sperner's theorem. Denoting by $\mathcal{P}(n, p)$ the $p$-random subset of the power set of $\{1, \ldots, n\}$, we show that, if $pn \to \infty$, the largest subset of $\mathcal{P}(n, p)$ containing no $k$-chain has size $(k - 1 + o(1))p\binom{n}{n/2}$ with high probability. The case $k = 2$ confirms a conjecture of Osthus.

The second chapter, which is joint work with Bushaw, Morris and Smith, focuses on a probabilistic result in additive combinatorics. We determine, for any even-order abelian group $G$, a sharp threshold for the following property: Each maximum-size sum-free subset of a $p$-random subset of $G$ is contained in a maximum-size sum-free subset of the whole of $G$. This strengthens a result of Balogh, Morris and Samotij.

The third chapter, which is joint work with Balogh, Bushaw, Liu, Morris and Sharifzadeh, contains a result on the typical structure of graphs in a certain family. We prove that, for $r \leq (\log n)^{1/4}$, almost every $K_{r+1}$-free graph on $n$ vertices is $r$-partite. This generalizes a result of Kolaitis, Pr\"omel and Rothschild, who obtained the same result for fixed $r$, and strengthens a result of Mousset, Nenadov and Steger, who computed the number of $K_{r+1}$-free graphs for the same range of $r$.

Anexos: