Yayılan Grafikler Oluşturma

Özet (abstract)

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.

Yazarların özeti; kaynağından alınmıştır. COMBINATORICA, 2026 · DOI ↗