# Online Talk: Natalie Behague

Tuesday, Oct 26, 3pm ET (8pm BST, 8am Wed NZST)
Natalie Behague, Ryerson University
Subgraph Games in the Semi-random Graph Process

##### Abstract:
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.

This site uses Akismet to reduce spam. Learn how your comment data is processed.