Making spanning graphs

Abstract

We prove that for each $D\ge 2$ there exists $c>0$ such that whenever $b\le c(\frac{n}{\log n}{)}^{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 $\frac{D-1}{2}$. This lower bound on the threshold bias is sharp up to the $\log$-factor when $H$ consists of $\frac{n}{3}$ vertex-disjoint triangles or $\frac{n}{4}$ vertex-disjoint $K_4$-copies.

10 pages

Cited by in corpus (1)

• Positional games on randomly perturbed graphs