Making Spanning Graphs
Abstract We prove that for each $$D\ge 2$$ D ≥ 2 there exists $$c>0$$ c > 0 such that whenever $$b\le c\big (\tfrac{n}{\log n}\big )^{1/D}$$ b ≤ c ( n log n ) 1 / D , in the (1 : b ) Maker-Breaker game played on $$E(K_n)$$ E ( K n ) , Maker has a strategy to guarantee claiming a graph G containing copies of all graphs H with $$v(H)\le n$$ v ( H ) ≤ n and $$\Delta (H)\le D$$ Δ ( H ) ≤ 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}$$ D - 1 2 . This lower bound on the threshold bias is sharp up to the $$\log $$ log -factor when H consists of $$\tfrac{n}{3}$$ n 3 vertex-disjoint triangles or $$\tfrac{n}{4}$$ n 4 vertex-disjoint $$K_4$$ K 4 -copies.
Authors
- Humberto Naves
- Yoshiharu Kohayakawa (ORCID: https://orcid.org/0000-0001-7841-157X)
- Julia Böttcher (ORCID: https://orcid.org/0000-0002-4104-3635)
- Yury Person (ORCID: https://orcid.org/0000-0002-3091-3025)
Institutions
- Technische Universität Ilmenau (DE)
- University of Minnesota (US)
- Universidade de São Paulo (BR)
- London School of Economics and Political Science (GB)
Publication Details
- Journal
- COMBINATORICA
- Published
- 2026-11-04
- DOI
- https://doi.org/10.1007/s00493-026-00228-9
- Citations
- 4
- Primary Topic
- Limits and Structures in Graph Theory
- Type
- article
- Field-Weighted Citation Impact
- 0.00
Funders
- National Science Foundation
- Deutscher Akademischer Austauschdienst
- Deutsche Forschungsgemeinschaft
- Fundação de Amparo à Pesquisa do Estado de São Paulo
- Coordenação de Aperfeiçoamento de Pessoal de Nível Superior
- Conselho Nacional de Desenvolvimento Científico e Tecnológico