Back to Search
Start Over
A non-trivial upper bound on the threshold bias of the Oriented-cycle game.
- Source :
-
Journal of Combinatorial Theory - Series B . Jan2017, Vol. 122, p21-54. 34p. - Publication Year :
- 2017
-
Abstract
- In the Oriented-cycle game, introduced by Bollobás and Szabó [7] , two players, called OMaker and OBreaker, alternately direct edges of K n . OMaker directs exactly one previously undirected edge, whereas OBreaker is allowed to direct between one and b previously undirected edges. OMaker wins if the final tournament contains a directed cycle, otherwise OBreaker wins. Bollobás and Szabó [7] conjectured that for a bias as large as n − 3 OMaker has a winning strategy if OBreaker must take exactly b edges in each round. It was shown recently by Ben-Eliezer, Krivelevich and Sudakov [6] , that OMaker has a winning strategy for this game whenever b < n / 2 − 1 . In this paper, we show that OBreaker has a winning strategy whenever b > 5 n / 6 + 1 . Moreover, in case OBreaker is required to direct exactly b edges in each move, we show that OBreaker wins for b ⩾ 19 n / 20 , provided that n is large enough. This refutes the conjecture by Bollobás and Szabó. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 00958956
- Volume :
- 122
- Database :
- Academic Search Index
- Journal :
- Journal of Combinatorial Theory - Series B
- Publication Type :
- Academic Journal
- Accession number :
- 119783428
- Full Text :
- https://doi.org/10.1016/j.jctb.2016.05.002