Asymptotic Thresholds for (a:b) Minimum-Degree Games
We investigate the (a : b) Maker–Breaker subgraph game played on the edge set of the complete graph Kn, where n, a, b ∈ N , and Maker’s objective is to construct a member of a prescribed family of graphs H, while Breaker aims to prevent this. In our study, Breaker moves fi rst, and H is taken to be either the family of connected spanning subgraphs or the family of spanning subgraphs with minimum-degree at least k = k(n). For the (a : b) minimum-degree-k game, we determine the asymptotically optimal threshold bias across a wide range of values for a. For the (a:b) connectivity game, we resolve an open problem posed by Hefetz et al. (2012) by identifying the exact leading term in the asymptotic behavior of the threshold bias when a = c ln n.
Vorschau
Rechte
Nutzung und Vervielfältigung:
Bitte beachten Sie, dass einzelne Bestandteile der Publikation anderweitigen Lizenz- bzw. urheberrechtlichen Bedingungen unterliegen können.