Let r >= 4 be an integer and consider the following game on the complete graph K-n for n is an element of rZ: 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 is an element of N 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 a 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 et al. who resolved the case r is an element of {3, 4} up to a logarithmic factor. (C) 2021 Elsevier Inc. All rights reserved.
NSTL
Elsevier
