2020/02/07 by Liebenau, Anita, Nenadov, Rajko
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2002.02578
Let r ≥ 4 be an integer and consider the following game on the complete graph Kn for n ∈ r ℤ: Two players, Maker and Breaker, alternately claim previously unclaimed edges of Kn such that in each turn Maker claims one and Breaker claims b ∈ ℕ edges. Maker wins if her graph contains a Kr-factor, that is a collection of n/r vertex-disjoint copies of Kr, and Breaker wins otherwise. In other words, we consider a b-biased Kr-factor Maker-Breaker game. We show that the threshold bias for this game is of order n2/(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 ∈ \3,4\ up to a logarithmic factor.