Shuffle-Exchange Conjecture (graph-theoretic form)

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

Let $k,n\geq2$, put $t=k^{n-1}$, and let $\operatorname{SE}(k,n)$ be the bipartite graph with ordered parts $U=\{u_0,\ldots,u_{t-1}\}$ and $V=\{v_0,\ldots,v_{t-1}\}$, in which $u_iv_j$ is an edge exactly when the least nonnegative residue of $j-ki$ modulo $t$ lies in $\{0,\ldots,k-1\}$. For $r\geq2$, form an $r$-stage graph by concatenating $r-1$ identical copies, identifying output vertex $v_i$ of each copy with input vertex $u_i$ of the next. A mask is any $k$-regular bipartite multigraph between the first and last parts. The network is rearrangeable if every mask can be routed by mutually edge-disjoint paths, one for each mask edge, with the prescribed endpoints and one vertex in each consecutive stage. Define $r(k,n)$ as the smallest such $r$.

Statement recorded in the supplied source.

Determine $r(k,n)$ for all $k,n\geq2$. In particular, is the proposed identity \[r(k,n)=2n-1\] valid for every $k,n\geq2$? [S2]

Short English statement

Determine the smallest number of identical shuffle-exchange stages that can route every prescribed k-regular end-to-end demand multigraph without sharing edges; test the 2n−1 proposal.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 3108 (OPG-37089). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Beneš, Václav E.; Folklore; Stone, Harold S., Shuffle-Exchange Conjecture (graph-theoretic form), Open Problem Garden, node 37089. Complete problem, discussion and bibliography (including mathematical image alt text). https://www.openproblemgarden.org/op/shuffle_exchange_conjecture_graph_theoretic_form.