# Beneš Conjecture (graph-theoretic form)

**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 ().

## Link to Beneš Conjecture

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

The equivalence is based on the natural bijection 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:

Simplicity of is equivalent to the condition , for all .

Uniformity of is equivalent to the existence of a permutation of such that , for all .

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

External connectivity of is equivalent to transitivity of .

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).

Consequently, rearrangeability of is equivalent to completeness of . Here is *complete* if it satisfies .

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.

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 completeness 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.

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

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

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