Shuffle-Exchange Conjecture (graph-theoretic form)
Status open medium confidence
The Shuffle-Exchange Conjecture ($r(k,n)=2n-1$) remains open in general. The case $k=2$, $n \le 4$ (i.e., networks up to $16 \times 16$) was established before the 2009 OPG posting, and the best known general upper bound remains approximately $3\log_2 N - 3$ stages — far from the conjectured $2\log_2 N - 1$. No verified post-2009 paper resolving or substantially advancing the general conjecture was found.
Reviewer notes. Most journal pages (SIAM, Springer, IEEE Xplore, ACM DL, ResearchGate) returned 403/418 errors or required authentication and could not be fetched. The arXiv search for shuffle-exchange rearrangeability returned no results, suggesting no recent arXiv preprints exist on this problem. The SIAM paper 'Rearrangeability of (2n-1)-Stage Shuffle-Exchange Networks' (DOI 10.1137/S0097539798344847) appears to date from ~1999 (pre-posting). The Springer paper on 7-stage 16x16 networks is from 2008 (pre-posting). Search engine AI summaries were inconsistent and potentially hallucinated claims of a full proof; no such proof could be independently verified. The OPG problem pages (both garden.irmacs.sfu.ca and openproblemgarden.org) were unreachable. Confidence is medium rather than high because direct access to several key references was blocked.
Discussion
A mask for the graph $ G:=(\text{SE}(k,n))^{r-1} $ is a $ k $ -regular bipartite multigraph with the bipartition $ \{U,V\} $ . The graph $ G $ is said to be rearrangeable if for every its mask there exists a collection, called routing , of corresponding mutually edge-disjoint paths in $ G $ connecting its end parts. (For simplicity, we do not provide here a more general definition for rearrangeability of graphs.) Note that $ G $ is a simple $ r $ -partite graph with $ r k^{n-1} $ vertices and $ (r-1)k^{n} $ edges, and any route for it consists exactly of $ k^{n} $ paths. Also, $ r(k,n)\le r $ is equivalent to rearrangeability of $ G $ . Figure 1. Examples of multistage Shuffle-Exchange graphs. For example, according to the conjecture, the graph $ (\text{SE}(2,3))^{4} $ (see Fig. 1) is rearrangeable, which is a well known result. The problem and conjecture are equivalent "graph-theoretic" forms of remarkable Shuffle-Exchange (SE) problem and conjecture due to the following identity (that is not hard to show by normal reasoning): Theorem $ r(k,n)=d(k,n) $ . The definition of $ d(k,n) $ and more on SE problem/conjecture including the other 2 main forms of them, combinatorial and group-theoretic, and a survey of results can be found here .
Bibliography
-
★
[S71]H.S. Stone, Parallel processing with the perfect shuffle , IEEE Trans. on Computers C-20 (1971), 153-161. -
★
[B75]V.E. Beneš, Proving the rearrangeability of connecting networks by group calculation , Bell Syst. Tech. J. 54 (1975), 421-434.