Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2406.11051 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910490454654976 |
|---|---|
| author | Fouadi, Adnane Ouali, Mourad El Srivastav, Anand |
| author_facet | Fouadi, Adnane Ouali, Mourad El Srivastav, Anand |
| contents | We study the $(a:b)$ Maker-Breaker subgraph game played on the edges of the complete graph $K_n$ on $n$ vertices, $n,a,b \in \mathbb{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_n$ 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)) \frac{an}{a+\ln(n)}$ in case of $a=o\left(\sqrt{\frac{n}{\ln(n)}}\right)$ 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 $\frac{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 $\left(1+o(1) \right)\frac{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\left(\sqrt{\frac{n}{\ln n}} \right)$ and $a=Ω\left(\sqrt{\frac{n}{\ln n}} \right)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_11051 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Asymptotically Optimal Threshold Bias for the $(a : b)$ Maker-Breaker Minimum Degree, Connectivity and Hamiltonicity Games Fouadi, Adnane Ouali, Mourad El Srivastav, Anand Combinatorics We study the $(a:b)$ Maker-Breaker subgraph game played on the edges of the complete graph $K_n$ on $n$ vertices, $n,a,b \in \mathbb{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_n$ 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)) \frac{an}{a+\ln(n)}$ in case of $a=o\left(\sqrt{\frac{n}{\ln(n)}}\right)$ 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 $\frac{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 $\left(1+o(1) \right)\frac{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\left(\sqrt{\frac{n}{\ln n}} \right)$ and $a=Ω\left(\sqrt{\frac{n}{\ln n}} \right)$. |
| title | Asymptotically Optimal Threshold Bias for the $(a : b)$ Maker-Breaker Minimum Degree, Connectivity and Hamiltonicity Games |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2406.11051 |