Draw a graph, having as its vertices the double permutations (sequences of two copies each of the numbers $$0$$ through $$n-1$$ such that the first copies of each number are in sorted order), and connect by an edge two sequences that differ by a single transposition of adjacent elements. What is the structure of this graph? I was naively expecting a $$1\times 3\times 5\times 7\dots$$ grid, coming from the enumeration of these objects as double factorials, but no.

It can be seen to be a medium in this example, for $$n=3$$, because it's a planar graph in which all interior faces are centrally symmetric, but what about larger values of $$n$$?

The answer is that the medium structure persists for all $$n$$. A double permutation is a linear extension of a partial order on the $$2n$$ symbols occurring in the sequence, where the partial order enforces the constraint on the ordering of the first copies of each number:

The linear extensions of any partial order, under transposition operations, form a medium, and therefore the graph of double permutations is a partial cube.

### Comments:

silkov:
2008-01-19T16:48:55Z
Wow