Making spanning graphs

Publication date 14 November 2017

Abstract: We prove that for each

D g e 2

there exists

c > 0

such that whenever

, 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) l e n

and

D e l t a (H) l e 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

f r a c D - 1 2

. This lower bound on the threshold bias is sharp up to the

l o g

-factor when

H

consists of

f r a c n 3

vertex-disjoint triangles or

f r a c n 4

vertex-disjoint

K_{4}

-copies.

This page was built for publication: Making spanning graphs