The semi-random graph process can be thought of as a one player game. Starting with an empty graph on $n$ vertices, in each round a random vertex $u$ is presented to the player, who chooses a vertex $v$ and adds the edge $uv$ to the graph. Given a graph property, the objective of the player is to force the graph to satisfy this property in as few rounds as possible.

 

We will consider the property of constructing a fixed graph $G$ as a subgraph of the semi-random graph. Ben-Eliezer, Gishboliner, Hefetz and Krivelevich proved that the player can asymptotically almost surely construct $G$ given $n^{1–1/d}w$ rounds, where $w$ is any function tending to infinity with $n$ and $d$ is the degeneracy of the graph $G$. We have proved a matching lower bound. I will talk about this result, and discuss a generalisation of our approach to semi-random hypergraphs. I will finish with some open questions.

 

This is joint work with Trent Marbach, Pawel Prałat and Andrzej Ruciński.