Subgraphs in Semi-random Graphs

Speaker: Natalie Behague

Date: Wed, May 25, 2022

Location: Online

Conference: Emergent Research: The PIMS Postdoctoral Fellow Seminar

Subject: Mathematics, Combinatorics

Class: Scientific


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 (hence 'semi-random'). The goal of the player is to construct a small fixed graph G as a subgraph of the semi-random graph in as few steps as possible. I will discuss this process, and in particular the asympotically tight bounds we have found on how many steps the player needs to win. This is joint work with Trent Marbach, Pawel Pralat and Andrzej Rucinski.