Asymptotically Optimal Threshold Bias for the $(a : b)$ Maker-Breaker Minimum Degree, Connectivity and Hamiltonicity Games

We study the $(a:b)$ Maker-Breaker subgraph game played on the edges of the complete graph Kₙ on n vertices, n,a,b ∈ N where the goal of Maker is to build a copy of a specific fixed subgraph H. In our work this is a spanning graph with minimum degree $k=k(n)$, a connected spanning subgraph or a Hamiltonian subgraph. In the $(a:b)$ game in each round Maker chooses a unclaimed edges of Kₙ and Breaker chooses b unclaimed edges. Maker wins, if he succeeds to build a copy of the subgraph under consideration, otherwise Breaker wins. For the k-minimum-degree, we present a winning strategy for Maker leading to a bound that generalizes a bound of Gebauer and Szab{\'o} for the $(1:b)$ case. Moreover, we give an explicit strategy for Breaker for b >(1+o(1)) an/a+ln(n) in case of a=o(√n/ln(n)) and k=o(ln(n)). Note that this bound is the same as the Maker bound presented by Hefetz et al. (2012) for the $(a:b)$ connectivity game, which implies that the asymptotic optimal bias for this game is an/a+ln(n). This resolves the open problem stated by these authors. We also study the $(a:b)$ Hamiltonicity game in which Maker's goal is to create a Hamiltonian subgraph. For the $(1:b)$ variant Krivelevich proved that (1+o(1) )n/ln n is the exact threshold bias. Controlling Breaker's vertex degree in the $(a:b)$ Maker-Breaker minimum degree game enables us to the asymptotic optimal generalized threshold bias for the $(a:b)$-game, both for a=o(√n/ln n ) and a=Ω(√n/ln n ).