Hypercubes, shuffle-exchange graphs and de Bruijn digraphs (Q1310233)

The hypercube \(Q_ n\), the teleprinter diagram \(T_ n\) and the shuffle- exchange graph \(S_ n\) all have the same vertex set, the set of \(2^ n\) binary strings of length \(n\). While \(Q_ n\) and \(S_ n\) are undirected, \(T_ n\) is a directed graph. The authors define the digraph \(D(G)\) of a graph \(G\), and the graph \(G(D)\) of a given digraph \(D\) in the usual way. Let \(F\) denote the pair of edges \(\{0^ n,0^{n-1} 1\}\) and \(\{1^ n,1^{n-1} 0\}\), that is, a labelled \(2K_ 2\). The authors investigate the intersection pattern of the edges/arcs of these graphs. In particular, they prove \[ E(S_ n)=E(S_ n) \cap[E(Q_ n) \cup (E(G(T_ n))-F)]. \] They also enumerate the number of cycles in some of these intersections, using Möbius inversion.