Importance: High ✭✭✭
 Author(s): Beneš, Václav E. Folklore Stone, Harold S.
 Subject: Combinatorics
 Keywords:
 Posted by: Vadim Lioubimov on: November 27th, 2009

Given integers , let be the smallest integer such that the symmetric group on the set of all words of length over a -letter alphabet can be generated as , where is the shuffle permutation defined by , and is the exchange group consisting of all permutations in preserving the first letters in the words.

Problem  (SE)   Find .
Conjecture  (SE)   .

This beautiful and difficult problem arises in switching networks theory and has important applications in parallel processing, sorting networks, card shuffling, etc. In this area it is perhaps the most famous open question which is at the center of the quest to understand the phenonemon of network rearrangeability. Both the problem and conjecture are referred to as Shuffle-Exchange (SE) ones. The case of SE problem (but not the conjecture) can be traced back to the work of Stone [S71], where he showed that . The upper bound is the central case of Beneš conjecture [B75], while the lower bound can be easily seen (it is also a special case of the stronger version [B75] of Beneš conjecture, which turned out to be generally false). Over more than three decades SE conjecture, especially its case , has received a lot of attention, mostly in the context of switching networks, with rather modest results.

Note that is equivalent to , for any integer . Furthermore, it is easy to see that the latter decomposition is equivalent to , where is the subgroup of consisting of all permutations which may only change the letters on the position in the words.

Also, the case of SE conjecture can be reformulated as the following

Theorem  ()   Every permutation of entries of a square matrix can be obtained in 3 steps as follows: first by permuting entries in the columns, then - in the rows, and then - in the columns again. Moreover, some permutations cannot be obtained in less than 3 of such steps.

(The parameter in the case of SE conjecture corresponds to the size of a matrix in the theorem.) Moreover, the general case of SE conjecture can be reformulated as a straightforward generalization of Theorem () to the -dimensional cubic matrices (of size ) stating that every permutation of entries of such a matrix can be obtained in steps in a similar way, and this number is generally a precise lower bound.

Theorem () holds as being easily equivalent to the special case of the following classical result when each part of the multigraph has size :

Theorem  (König)   A -regular bipartite multigraph is -edge-colorable.

The function admits 3 main interpretations (that are not immediately equivalent), "group-theoretic" (presented in the beginning), "combinatorial" (below), and "graph-theoretic", each of which provides its own framework for SE problem and suggests its own interesting natural generalizations and extensions. Accordingly, there are 3 equivalent forms of SE problem/conjecture. Although the group-theoretic interpretation of is the shortest and most elegant among the three, it seems the least natural when it comes to proving the known results and studying SE problem more deeply. I believe that SE problem is very deep and combinatorial by nature. I also strongly believe in the validity of SE conjecture.

## 2. Combinatorial form of SE problem/conjecture

Given a pure abstract simplicial complex of rank and a positive integer , an -transition is a map that assigns to evey pair of ordered facets, and , a sequence of vertices such that every -segment of the sequence forms a facet. Let be the smallest , or if none exists, for which there exists an -transition. Note that is equivalent to the existence of -transition for , for any .

Given integers , let be the pure abstract simplicial complex of rank whose vertex set is the set of all uniform -partitions (i.e., ones consisting of equal-sized blocks) of a -set, and whose facets are all -subsets of with zero infinum. Using normal reasoning, it is not hard to show [L04] the following

Theorem   .

Thus, the combinatorial forms of SE problem and conjecture can be formulated as to find and that , respectively.

The infinum (or meet) of two partitions and of a set is the partition of defined by

Note that together with the operation , the collection of all partitions of forms a semilattice (i.e., a commutative and idempotent semigroup) with the identity and zero being the partitions and , respectively.

Observe that the complex is non-matroidal for all .

## 3. Constructive version of SE problem/conjecture

Application-wise it is important not only to establish a certain decomposition or, equivalently, rearrangeability of the graph or, equivalently, the existence of an -transition for the complex , but also to find a corresponding efficient factorization/routing/transition algorithm.

Given an identity , where all are subsets of a multiplicative group, a factorization algorithm finds for every an -tuple such that . Given a rearrangeable graph , a routing algorithm takes a mask of the graph as input and returns a corresponding routing. Given a pure simplicial complex with , an -transition algorithm realizes an -transition for . It is not hard to prove

Theorem   Any factorization algorithm for translates into a routing algorithm for and into an -transition algorithm for of the same complexity, and vise versa. Consequently, .

Here , , and are the sets of all , respectively, for which there exists an efficient polynomial-time (in ) factorization/routing/transition algorithm mentioned in the above theorem (we will also write to indicate the existence of such a factorization algorithm for , where each ). Clearly,

where with the usual convention , and is defined here.

It is easy to see that implies (equivalently, the same is true for and ). Consequently, is equivalent to .

Problem  (CSE)   Find (or estimate) and specify the corresponding factorization/routing/transition algorithm for the upper bound.
Conjecture  (CSE)   .

Both the problem and conjecture are referred here to as Constructive Shuffle-Exchange (CSE) ones. The conjecture was proposed in [L04]. Clearly, CSE conjecture implies SE one as .

## 4. Main results

So far SE/CSE conjecture has been only settled in the following 3 cases: , , and . That is, the following 3 identities holds:

Also, there are 2 the following major results on SE/CSE problem:

• (4) .
• (5) , if .

The lower bound (4) follows immediately from the obvious observation that , for any pure complex .

Note that (4) reduces SE (CSE) conjecture to which is equivalent to . In fact, the main reason why SE/CSE conjecture is widely believable, apart from results (1-4), is a close similarity between the latter decomposition and the following well known result [B65, L04] (that is not hard to derive from the constructive version of the König's theorem):

Theorem  (Beneš)   .

Combining (1) and (3) with (5) yields respectively the following 2 best known upper bounds (in addition to (2)) for both and :

• .
• , if .

As it was mentioned earlier, the case of SE conjecture is easily equivalent to the following case of the Konig's theorem: a -regular bipartite multigraph with -vertex parts is -edge-colorable. Moreover, any -edge-coloring algorithm for the graph easily translates into a factorization/routing/1-transition algorithm of the same complexity for (at ) or the graph or the complex , respectively, and vise versa. Consequently, as there are many efficient polynomial-time (in ) -edge-coloring algorithms well known for the graph , the case of CSE conjecture also holds.

There are at least 6 alternative proofs proposed for the case of CSE conjecture. Although they may look quite different, each proof is essentially based on either of 3 similar short and elegant algorithms which we refer to as A1 [RV87, LT89, L04], A2 [ND00, L04] and A3 [KR91]. Each algorithm is based on a 2-edge-coloring algorithm for a 2-regular bipartite multigraph with 4-vertex parts. Namely, A1 uses 2, A2 uses at most 2, and A3 uses 1 application(s) of such an algorithm. Each algorithm Ai deals with 2 cases in which the procedure is especially simple. The algorithms A1 and A2 are very efficient (with A2 being slightly faster than A1), while A3 is not so (contrary to what is claimed in [KR91]) as it relies on an exhausting search to determine the case for each input permutation. However, A3 has some theoretical advantage over A1 and A2 as its 2 cases partition the symmetric group into 2 classes that do not depend on a realization of the algorithm. In [L04], both algorithms A1 and A2 are explicitly described as 2-transition algorithms for the complex , and the corresponding 2 proofs for the statement are particularly transparent. Moreover, the latter statement, the algorithms and the proofs are straightforwardly generalized [L05] to a wide class of 2-dimensional pure abstract simplicial complexes.

A brute force verification for the case of SE conjecture was first reported in [R95]. The first theoretical proof for such case of CSE conjecture was proposed (in graph-theoretic terms) in [ND00]. Although the ideas behind the underlying algorithm for this proof are simple, the algorithm deals with a huge and intricate tree of cases and is substantially more complicated (and not so elegant) than that of the case . As a result, the proof is very tedious, hard to verify, and leaves little hope for using a similar approach to prove the next case of CSE conjecture. An essentially similar but slightly better organized algorithm and proof for (3) were proposed in [DS08] (with no reference to [ND00]).

The upper bound (5) was first obtained in [VR88] for the case and (i) . In other words, it was shown that (i) at implies , if . A much simpler proof of (5) for the case and (i) appeared in [LT89]. The latter proof was easily extended [ND00] to an arbitrary . A transparent combinatorial proof in terms of the complex for the general case of (5) was proposed in [L04]. This proof (together with its underlying transition algorithm) was generalized [L05] to a wide class of pure abstract simplicial complexes of arbitrary dimensions. Namely, it was shown that, given a complex in this class and an integer ,

and, moreover, that any -transition algorithm for the complexes can be efficiently used to make a -transition algorithm for . Note that (5) can be easily obtained as an instance of the latter result. Here is the link of a face in , i.e., a subcomplex of defined by

It is worth noting that there are many flawed proofs for SE conjecture in the literature. Most notably, in [Ba01] (the general case) and [C03] (the case ). The latter proof was first refuted in [BHL06], while the former remains unrefuted in the literature.

## Bibliography

[B65] V.E. Benes, Mathematical theory of connecting networks and telephone traffic, Academic Press, New York, 1965.

*[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.

[RV87] C.S. Raghavendra, A. Varma, Rearrangeability of 5-stage shuffle/exchange network for N=8, IEEE Trans. on Commun. COM-35 (1987), 808-812.

[VR88] A. Varma, C.S. Raghavendra, Rearrangeability of multistage shuffle/exchange networks, IEEE Trans. on Commun. 36 (1988), 1138-1147.

[LT89] N. Linial, M. Tarsi, Interpolation between bases and the shuffle-exchange networks, European J. of Combinatorics, 10(1) (1989), 29-39.

[KR91] K. Kim, C.S. Raghavendra, A Simple Algorithm to Route Arbitrary Permutations on 8-input 5-stage Shuffle/Exchange Network, Proc. 5th International Parallel Processing Symposium (1991), 398-403.

[R95] C.S. Raghavendra, On the rearrangeability conjecture of -stage shuffle/exchange network, IEEE Computer Society, Tech. Committee on Comp. Arch. Newsletter, Position paper (Winter 1995), 10-12.

[ND00] H.Q. Ngo, D.Z. Du, On the rearrangeability of shuffle-exchange networks, Tech. Report TR00-045, Dept. of Computer Science, Univ. of Minnesota (2000)

[Ba01] R.E. Bashirov, On the rearrangeability of 2s-1 stage networks employing uniform interconnection pattern Calcolo, Springer Verlag, 38(2) (2001), 85-97.

[C03] H. Cam, Rearrangeability of (2n-1)-stage shuffle-exchange networks, SIAM J. on Computing 32(3) (2003), 557-585.

[L04] V. Lioubimov, Decomposition of symmetric group into product of stabilizers and Shuffle-Exchange problem, manuscript (2004).

[L05] V. Lioubimov, Facet transitions in abstract simplicial complexes, manuscript (2005).

[BHL06] X. Bao, F.K. Hwang, Q. Li, Rearrangeability of bit permutation networks, Theoretical Computer Science, 352(1) (2006), 197-214.

[DS08] H. Dai, X. Shen, Rearrangeability of 7-stage 16x16 shuffle-exchange networks, Frontiers of Electrical and Electronic Engineering in China, 3(4) (2008), 440-458.

* indicates original appearance(s) of problem.