# Szymanski's Conjecture - Routing Permutations in Hypercubes (1989)

Originator(s): T. Szymanski (presented by West - REGS 2008)

Definitions:

Conjecture: If σ is a permutation of the vertices of the d-dimensional hypercube Qd, then there exist v,σ(v)-paths in the doubly directed version of Qd that are pairwise edge-disjoint. That is, each edge is used by at most one path in each direction.

Background/motivation: The ability to route arbitrary permutations models communication of information in a network of processors. The hypercube is a natural architecture for such processors. The problem also is a special case of a multicommodity flow problem.

Comments/Partial results: Szymanski [S] proved the conjecture through dimension 3, with the stronger property that all paths were shortest paths. Lubiw [L] provided an example in dimension 5 that cannot be routed using shortest paths, and Darmet [D] gave such an example in dimension 4.

In [BFH], the conjecture is proved for dimension 4. However, this proof is by computer search, using symmetries to reduce to finding paths for 32×40320 permutations.

The problem has been solved for permutations that are involutions. Here one can seek solutions that use the same path in both directions, though the problem does not require such special paths. Sprague and Tamaki [ST] proved this such solutions exist for all involutions in odd dimensions and for all involutions in even dimensions except the involution that sends every vertex to its complement (antipode) and one other nearly antipodal involution. Solutions without using the same path in both directions exist for these involutions (note the 2-dimensional example).

The requirement of edge-disjointness in the paths makes this problem very difficult. A more tractible model of routing permutations on graphs considers routing by matchings in the minimum number of rounds.

References:
[BFH] Baudon, Olivier; Fertin, Guillaume; Havel, Ivan; Routing permutations in the hypercube. Graph-theoretic concepts in computer science (Ascona, 1999), 179--190, Lecture Notes in Comput. Sci., 1665, Springer, Berlin, 1999.
[D] A. Darmet, Private communication. 1992.
[L] A. Lubiw, Counterexample to a conjecture of Szymanski on hypercube routing, Inform. Process. Lett. 35 (1990) 57--61.
[ST] A.P. Sprague, H. Tamaki, Routing for involutions of a hypercube, Discrete Appl. Math. 48 (1994) 175--186.
[S] T. Szymanski, On the permutation capability of a circuit-switched hypercube, Proceedings of the International Conference on Parallel Processing, 1989.