2024/06/16 by Adnane Fouadi, Fouadi, Adnane, Mourad El Ouali +3 · 1 citation
Computer Science · Mathematics · #Optimization and Search Problems #Markov Chains and Monte Carlo Methods #Complexity and Algorithms in Graphs
paper · pdf · doi:10.48550/arxiv.2406.11051
We study the (a:b) Maker-Breaker subgraph game played on the edges of the complete graph Kn on n vertices, n,a,b ∈ ℕ 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 Kn 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ó 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)) ).