Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2503.16770 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912285638787072 |
|---|---|
| author | Liebenau, Anita Saffidine, Abdallah Yang, Jeffrey |
| author_facet | Liebenau, Anita Saffidine, Abdallah Yang, Jeffrey |
| contents | We study the $b$-biased Oriented-cycle game where two players, OMaker and OBreaker, take turns directing the edges of $K_n$ (the complete graph on $n$ vertices). In each round, OMaker directs one previously undirected edge followed by OBreaker directing between one and $b$ previously undirected edges. The game ends once all edges have been directed, and OMaker wins if and only if the resulting tournament contains a directed cycle. Bollobás and Szabó asked the following question: what is the largest value of the bias $b$ for which OMaker has a winning strategy? Ben-Eliezer, Krivelevich and Sudakov proved that OMaker has a winning strategy for $b \leq n/2 - 2$. In the other direction, Clemens and Liebenau proved that OBreaker has a winning strategy for $b \geq 5n/6+2$. Inspired by their approach, we propose a significantly stronger strategy for OBreaker which we prove to be winning for $b \geq 0.7845n + O(1)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_16770 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | An Improved Upper Bound on the Threshold Bias of the Oriented-cycle game Liebenau, Anita Saffidine, Abdallah Yang, Jeffrey Combinatorics 05C20, 05C57 We study the $b$-biased Oriented-cycle game where two players, OMaker and OBreaker, take turns directing the edges of $K_n$ (the complete graph on $n$ vertices). In each round, OMaker directs one previously undirected edge followed by OBreaker directing between one and $b$ previously undirected edges. The game ends once all edges have been directed, and OMaker wins if and only if the resulting tournament contains a directed cycle. Bollobás and Szabó asked the following question: what is the largest value of the bias $b$ for which OMaker has a winning strategy? Ben-Eliezer, Krivelevich and Sudakov proved that OMaker has a winning strategy for $b \leq n/2 - 2$. In the other direction, Clemens and Liebenau proved that OBreaker has a winning strategy for $b \geq 5n/6+2$. Inspired by their approach, we propose a significantly stronger strategy for OBreaker which we prove to be winning for $b \geq 0.7845n + O(1)$. |
| title | An Improved Upper Bound on the Threshold Bias of the Oriented-cycle game |
| topic | Combinatorics 05C20, 05C57 |
| url | https://arxiv.org/abs/2503.16770 |