Graphs and Matroid Seminar - Hidde Koerts

Title: k-Connectedness and k-Factors in the Semi-Random Graph Process

Abstract: The semi-random graph process is a single player graph game where the player is initially presented an edgeless graph with n vertices. In each round, the player is offered a vertex u uniformly at random and subsequently chooses a second vertex v deterministically according to some strategy, and adds edge uv to the graph. The objective for the player is then to ensure that the graph fulfils some specified property as fast as possible.

We investigate the properties of being k-connected and containing a k-factor. We settle the open case for 2-connectedness by showing that the player has a strategy to construct a 2-connected graph asymptotically almost surely in (ln 2 + ln(ln 2 + 1) + o(1))n rounds, which matches a known lower bound asymptotically. We also provide a strategy for building a k-factor in asymptotically almost surely (β + 10^(-5))n rounds, where β is derived from the solution of a system of differential equations.

Joint work with Jane Gao.