Szymanski's conjecture
In mathematics, Szymanski's conjecture, named after, states that every permutation on the n-dimensional doubly directed hypercube graph can be routed with edge-disjoint paths. That is, if the permutation σ matches each vertex v to another vertex σ, then for each v there exists a path in the hypercube graph from v to σ such that no two paths for two different vertices u and v use the same edge in the same direction.
Through computer experiments it has been verified that the conjecture is true for n ≤ 4. Although the conjecture remains open for n ≥ 5, in this case there exist permutations that require the use of paths that are not shortest paths in order to be routed.
