Sorting by shuffling methods and a queue

08.06.2021 15:15 - 16:45

Stoyan Dimitrov (University of Illinois at Chicago)

Abstract: We consider sorting by a queue that can apply a permutation from a given set over its content. This gives us a sorting device $\mathbb{Q}_{\Sigma}$ corresponding to any shuffling method $\Sigma$ since every such method is associated with a set of permutations. Two variations of these devices are considered - $\mathbb{Q}_{\Sigma}^{\prime}$ and $\mathbb{Q}_{\Sigma}^{\text{pop}}$. These require the entire content of the device to be unloaded after a permutation is applied or unloaded by each pop operation, respectively.

First, we show that sorting by a deque is equivalent to sorting by a queue that can reverse its content. Next, we focus on sorting by cuts, which has significance in computational biology and a natural interpretation. We prove that the set of permutations that can be sorted by using $\mathbb{Q}_{\text{cuts}}^{\prime}$ is the set of the 321-avoiding separable permutations. We also give lower and upper bounds to the maximum number of times the device must be used to sort a permutation. These are analogues of the bounds previously obtained by Eriksson et al.

Furthermore, we give a formula for the number of n-permutations that one can sort by using $\mathbb{Q}_{\Sigma}^{\prime}$, for any shuffling method $\Sigma$, such that the permutations associated with it are irreducible. The rest of the work is dedicated to a surprising conjecture inspired by Diaconis and Graham which states that one can sort the same number of permutations of any given size by using the devices $\mathbb{Q}_{\text{In-sh}}^{\text{pop}}$ and $\mathbb{Q}_{\text{Monge}}^{\text{pop}}$, corresponding to the popular In-shuffle and Monge shuffling methods.

Meeting-ID: 945 4121 9182, Kenncode: Let2Vh 


Ch. Krattenthaler

Zoom Meeting