Hurlbert's ordering conjecture for universal cycles of permutations

Let SnS_n be the set of permutations of [n][n], and let O(n)\mathcal{O}(n) be the clustered graph of overlapping nn-permutations: its edges are the permutations in SnS_n, and consecutive permutations overlap in their last and first n1n-1 entries up to reduction. Hurlbert's ordering conjecture. Given any Euler tour of the clustered graph of overlapping permutations (that is, an ordering of SnS_n such that each consecutive pair of permutations overlaps), there is a universal cycle for permutations that covers SnS_n in the same order. Universal cycles correspond to Euler tours in this graph, but it remains open whether every such ordering can be realized by a universal cycle.

Sources & referencesView supporting material

Primary source

Rachel Kirsch, Clare Sibley and Elizabeth Sprangel, “Graph Universal Cycles: Compression and Connections to Universal Cycles”, arXiv:2209.14198 (2022).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.