A medium of double permutations

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: