TOPICS
Search

Oriented-Cycle Game


The oriented-cycle game is a two-player game on the edges of a complete graph K_n. OMaker moves first and directs one unused edge per turn. In the monotone b-biased version, OBreaker then directs between one and b unused edges. OMaker wins if the final tournament contains a directed cycle, and OBreaker wins otherwise (Liebenau et al. 2026).

Let t(n) be the largest integer bias for which OMaker has a winning strategy. Allowing OBreaker fewer than b edges makes the game monotone in b. The strict version, in which OBreaker must direct exactly b edges when available, is a different game.

The bounds

 n/2-2<=t(n)<=0.7841n+O(1)

combine the OMaker strategy of Ben-Eliezer et al. (2012) with the improved OBreaker strategy of Liebenau et al. (2026). The latter improves the earlier coefficient 5/6 for the monotone version.


See also

Complete Graph, Tournament

Explore with Wolfram|Alpha

References

Ben-Eliezer, I.; Krivelevich, M.; and Sudakov, B. "Biased Orientation Games." Disc. Math. 312, 1732-1742, 2012.Liebenau, A.; Saffidine, A.; and Yang, J. "An Improved Upper Bound on the Threshold Bias of the Oriented-Cycle Game." Electron. J. Combin. 33, P3.59, 2026. https://doi.org/10.37236/14172.

Cite this as:

Weisstein, Eric W. "Oriented-Cycle Game." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Oriented-CycleGame.html

Subject classifications