Making spanning graphs
Add this Pith Number to your LaTeX paper
What is a Pith Number?\usepackage{pith}
\pithnumber{MVQ56I7X}
Prints a linked pith:MVQ56I7X badge after your title and writes the identifier into PDF metadata. Compiles on arXiv with no extra files. Learn more
read the original abstract
We prove that for each $D\ge 2$ there exists $c>0$ such that whenever $b\le c\big(\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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.