pith. the verified trust layer for science. sign in

arxiv: 1711.05311 · v1 · pith:MVQ56I7Xnew · submitted 2017-11-14 · 🧮 math.CO

Making spanning graphs

classification 🧮 math.CO
keywords tfraccopiesgraphgraphsstrategyvertex-disjointbiasbound
0
0 comments X p. Extension
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.