加载中…
Let be an integer and consider the following game on the complete graph for : Two players, Maker and Breaker, alternately claim previously unclaimed edges of such that in each turn Maker claims one and Breaker claims edges. Maker wins if her graph contains a -factor, that is a collection of vertex-disjoint copies of , and Breaker wins otherwise. In other words, we consider a -biased -factor Maker-Breaker game. We show that the threshold bias for this game is of order . 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 up to a logarithmic factor.

生成讲解博客的中文版本

生成AI智能校验的中文版本