The threshold bias of the clique-factor game

20 October 2020
10:30
Anita Liebenau

Further Information: 

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

Abstract

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.

  • Combinatorial Theory Seminar