Date
Tue, 20 Oct 2020
10:30
Location
Virtual
Speaker
Anita Liebenau
Organisation
UNSW

Let $r>3$ be an integer and consider the following game on the complete graph $K_n$ for $n$ a multiple of $r$: Two players, Maker and Breaker, alternately claim previously unclaimed edges of $K_n$ such that in each turn Maker claims one and Breaker claims $b$ edges. Maker wins if her graph contains a $K_r$-factor, that is a collection of $n/r$ vertex-disjoint copies of $K_r$, and Breaker wins otherwise. In other words, we consider the $b$-biased $K_r$-factor Maker-Breaker game. We show that the threshold bias for this game is of order $n^2/(r+2)$. This makes a step towards determining the threshold bias for making bounded-degree spanning graphs and extends a result of Allen, Böttcher, Kohayakawa, Naves and Person who resolved the case $r=3$ or $4$ up to a logarithmic factor.
    Joint work with Rajko Nenadov.

Further Information

Part of the Oxford Discrete Maths and Probability Seminar, held via Zoom. Please see the seminar website for details.

Please contact us with feedback and comments about this page. Last updated on 03 Apr 2022 01:32.