We prove that for each $Dge 2$ there exists $c>0$ such that whenever $ble cbig(tfrac{n}{log n}big)^{1/D}$, in the $(1:b)$ Maker-Breaker game played on $E(K_n)$, Maker has a strategy to guarantee claiming a graph $G$ containing copies of all graphs $H$ with $v(H)le n$ and $Delta(H)le D$. We show further that the graph $G$ guaranteed by this strategy also contains copies of any graph $H$ with bounded maximum degree and degeneracy at most $tfrac{D-1}{2}$. This lower bound on the threshold bias is sharp up to the $log$-factor when $H$ consists of $tfrac{n}{3}$ vertex-disjoint triangles or $tfrac{n}{4}$ vertex-disjoint $K_4$-copies.
تحميل البحث