Sortability of Permutations in the Presence of an Adversary

Manaswinee Bezbaruah, Leigh Foster, Henry Fessler, George Spahn, Marion Scheepers

Research output: Contribution to conferencePresentation

Abstract

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't 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.

Original languageAmerican English
StatePublished - 12 Jul 2018

Fingerprint

Dive into the research topics of 'Sortability of Permutations in the Presence of an Adversary'. Together they form a unique fingerprint.

Cite this