Contents Online

# Pure and Applied Mathematics Quarterly

## Volume 18 (2022)

### Number 6

### Special issue in honor of Fan Chung

Guest editors: Paul Horn, Yong Lin, and Linyuan Lu

### On the generalized shuffle-exchange problem

Pages: 2619 – 2645

DOI: https://dx.doi.org/10.4310/PAMQ.2022.v18.n6.a13

#### Authors

#### Abstract

We investigate the *shuffle-exchange* problem in this paper: given a permutation $\pi$ on $[n] \times [m]$ and two permutation groups $G$ on $[n]$ and $H$ on $[m]$, the goal is to generate $\pi$ by alternately using the following two types of operations:

• Select $g_1, g_2, \dotsc , g_m \in G$ and perform each $g_i$ on the $i$-th column of $[n] \times [m]$ in parallel;

• Select $h_1, h_2, \dotsc, h_n \in H$ and perform each $h_j$ on the $j$-th row of $[n] \times [m]$ in parallel.

We discuss the shuffle-exchange, i.e., the composition of these allowable operations, from the perspective of the *Cayley graph*.

For cases where the base groups G and H are both cyclic groups, we prove that the diameter of the underlying Cayley graph, i.e., the minimum number of steps sufficient to achieve any permutation, is upper bounded by $O (\min {\lbrace n + m, n \log m, m \log n \rbrace})$, which is asymptotically optimal when $\min {\lbrace n, m \rbrace} = O(1)$ or $n = \Theta (m)$. The main idea is to simulate the shuffle-exchange over symmetric groups with cyclic operations and further accelerate the process with the low-depth *periodic switching network*. For the shuffle-exchange over general groups, we characterize the reachability of any two given vertices on the Cayley graph, and prove the minimum number of steps to achieve a permutation, if possible, is $O(nm)$. This implies that though a connected component of the Cayley graph could contain exponential number of vertices, its diameter is only at most a polynomial of $n, m$.

This work was supported in part by the National Natural Science Foundation of China Grant No. 61832003, 61872334, the Strategic Priority Research Program of Chinese Academy of Sciences Grant No. XDB27000000.

Received 27 July 2021

Received revised 30 August 2022

Accepted 18 September 2022

Published 29 March 2023