Natalie Behague

Subgraph Games in the Semi-random Graph Process

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 et al. 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.