Importance: High ✭✭✭
 Author(s): Beneš, Václav E.
 Subject: Graph Theory
 Keywords:
 Posted by: Vadim Lioubimov on: April 17th, 2010
Problem  ()   Find a sufficient condition for a straight -stage graph to be rearrangeable. In particular, what about a straight uniform graph?
Conjecture  ()   Let be a simple regular ordered -stage graph. Suppose that the graph is externally connected, for some . Then the graph is rearrangeable.

Given an integer , an -stage graph is an -partite graph with a list of its parts such that every edge of has endpoints in both and , for some . A vertex in () is a source (target) of . A path in is plain if it goes from a source to a target through each part of exactly once. The graph is externally connected if for every source and target there exists a plain path from to . A mask for is a -stage multigraph whose sources and targets are exactly those of and such that every vertex of has the same degree in . The graph is rearrangeable if for every its mask there exists a collection, called routing, of corresponding mutually edge-disjoint plain paths in .

The graph is ordered if each of its parts is linearly ordered. The graph is uniform and denoted if there is an ordered 2-stage graph with equal-sized parts such that is the proper (i.e., respecting all the orders in ) concatenation of identical copies of . The graph is straight if for any and any , the number of edges joining with equals that of .

Conjecture () can be reformulated as , where () denotes the smallest positive integer , or if none exists, such that the graph is rearrangeable (externally connected).

## Examples

Consider the simple 2-regular -stage ordered graphs shown in Fig.1. It is easy to see that and (the corresponding externally connected graphs are depicted in blue). Therefore, according to Conjecture (), the graphs should be rearrangeable, which is indeed the case. The graph is the 2-stage Shuffle-exchange graph , and there are several nice proofs known for . Although I am not aware of any theoretical proof for rearrangeability of or , I have verified by brute force without difficulty that and .

Figure 1. Examples for Conjecture ().

Problem () and Conjecture () are equivalent "graph-theoretic" forms of Problem () and Beneš conjecture [B75], respectively.

The equivalence is based on the natural bijection (up to isomorphism) between the -systems of partitions and the straight -stage graphs, given any . Here an -system of partitions is an -tuple of partitions of some finite set . The image of under this bijection is the straight -stage graph denoted and defined as follows. The edge set of is , the th vertex part is , for all , and the edge-vertex incidence is such that every edge has endpoints and uniquely determined by .

The bijection provides a convenient two-way link between the frameworks for Problems () and () via numerous easily seen equivalences. Here is some basic ones:

\item Simplicity of is equivalent to the condition , for all . \item Uniformity of is equivalent to the existence of a permutation of such that , for all .

\item -quasi-regularity of is equivalent to every block of being of size , for all . Here the graph is -quasi-regular if the induced bipartite subgraph on is -regular, for all . Note that a quasi-regular multistage graph is straight. Also, -quasi-regularity of is equivalent to -regularity of .

\item External connectivity of is equivalent to transitivity of .

\item Given a permutation of , the membership is equivalent to routability of the mask for defined as follows. The edge set of is and the edge-vertex incidence is such that every edge has endpoints and uniquely determined by . Note that given , the map is surjective (but generally not injective).

\item Consequently, rearrangeability of is equivalent to universality of . Here is universal if it satisfies .

\item If is rearrangeable, then any routing algorithm for easily translates to a factorization algorithm of the same complexity for the latter identity, and vise versa. Here, given a rearrangeable multistage graph, a routing algorithm is one that takes a mask of the graph as input and returns a corresponding routing.

\item Contracting all edges between and in is equivalent to replacing the partitions and in with their supremum , given any fixed . In other words, , where is the contracted graph and . In fact, the procedure preserves universality of , as . Equivalently, the procedure preserves rearrangeability of .

## Counterexamples

Although the presented graph-theoretic statement () of Problem () may look more complex, it provides somewhat more intuitive framework to study the problem and, in particular, Beneš conjecture. To illustrate this, let us now reconsider in terms of this framework and in more detail the 3 counterexamples for some extensions of Beneš conjecture discussed here.

1. The condition of simplicity of the graph (essentially missing in the original statement [B75] of Beneš conjecture) is necessary for Conjecture (). To see this, consider the following 2-stage 3-regular non-simple ordered graph :

Whereas is obviously externally connected, the graph is not rearrageable. This is because it is evidently impossible to connect the two red vertices in (a source and a target) with 3 mutually edge-disjoint plain paths.

2. Conjecture () is not directly generalizable to non-uniform graphs. More precisely, the condition of uniformity of is necessary for the following reformulation of ():

Conjecture   Let be a simple quasi-regular ordered multistage graph. Suppose that is uniform and externally connected. Then the graph is rearrangeable.

Here denotes the proper concatenation of 2 identical copies of . To see the necessity, consider the following simple 4-stage 2-quasi-regular non-uniform ordered graph :

Whereas is obviously externally connected, the graph is not rearrangeable. To see this, recall that contracting all edges between two consecutive parts in a straight multistage graph preserves its rearrangeability. Therefore, if were rearrangeable then so would be the 3-stage graph obtained from by contracting all edges in the shadowed areas. However, this is not true as it is evidently impossible to connect the two red vertices in (a source and a target) with 4 mutually edge-disjoint plain paths.

3. The stronger version of Conjecture () (proposed essentially in the same paper [B75]), claiming that , is false. The graph shown in Fig.1 is a counterexample as .

More information on Problem () and Conjecture () can be found here (via Problem () and Beneš conjecture).

## Bibliography

*[B75] V.E. Beneš, Proving the rearrangeability of connecting networks by group calculation, Bell Syst. Tech. J. 54 (1975), 421-434.

* indicates original appearance(s) of problem.