Sortability of Permutations in the Presence of an Adversary

Ciliates are single-cell organisms with two nuclei. The DNA sorting processes that naturally occur in ciliates are analogous to two particular operations on permutations. These sorting operations are of combinatorial interest outside of biology. The operations are efficient but cannot sort everything. We look at the sortability of permutations through the lens of graph theory and matrices. If a permutations is sortable, we show that any possible sequence of these operations will sort it and give an efficient algorithm for determining sortability. In the unsortable case, this algorithm gives the possible termination states that can result from these sorting operations. In the cases where sorting doesn\u27t work, we can represent the interactions between permutations from a game theoretic point of view. We examine one- and two-player games based on these permutations, and develop techniques for determining a winning strategy