Permutation sorting and a game on graphs

C. L. Jansen, M. Scheepers, S. L. Simon, E. Tatum

Published 2014-11-20Version 1

We introduce a game on graphs. By a theorem of Zermelo, each instance of the game on a finite graph is determined. While the general decision problem on which player has a winning strategy in a given instance of the game is unsolved, we solve the decision problem for a specific class of finite graphs. This result is then applied to a permutation sorting game to prove the optimality of a proportional bound under which TWO has a winning strategy.