Hurlbert's ordering conjecture for universal cycles of permutations
Let be the set of permutations of , and let be the clustered graph of overlapping -permutations: its edges are the permutations in , and consecutive permutations overlap in their last and first entries up to reduction. Hurlbert's ordering conjecture. Given any Euler tour of the clustered graph of overlapping permutations (that is, an ordering of such that each consecutive pair of permutations overlaps), there is a universal cycle for permutations that covers 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.
References
- Rachel Kirsch, Clare Sibley and Elizabeth Sprangel, “Graph Universal Cycles: Compression and Connections to Universal Cycles”, arXiv:2209.14198 (2022).
Progress summary
A reader-submitted claim says the conjecture is false in four dimensions, but this alleged counterexample has not been independently verified.
The conjecture asks whether every ordering of all permutations arising from an Euler tour can be produced by one cyclic word. It is attributed to Hurlbert and remains recorded as open in the previously catalogued literature.
Community submission (unverified), November 7, 2026
A submitted proof argues that an explicit Euler tour of the full overlap graph cannot be realized by any cyclic word over a linearly ordered alphabet: nine windows allegedly force a strict comparison cycle. If correct, this would refute the conjecture at , without addressing whether universal cycles themselves exist.
Current status (as of November 2026): The conjecture remains open in independently retrieved sources; a November 2026 community submission claims an unverified counterexample at .
Sources
Solutions 1
Hurlbert's ordering conjecture (Kirsch-Sibley-Sprangel Conjecture 6.3; Hurlbert 1990; the Chung-Diaconis-Graham 1992 belief) is false at n = 4: an explicit Euler tour of the clustered overlap graph O(4) is realized by no cyclic word over any linearly ordered alphabetSee full solution
An explicit Euler tour of the full clustered overlap graph O(4) visits all 24 permutation edges, but nine of its windows force a strict comparison cycle. No cyclic word over any linearly ordered alphabet can realize that tour. This refutes the assertion that every such Euler tour is realizable; it does not deny the existence of universal cycles. The comparison-digraph method is classical; the contribution is this obstruction for the full permutation graph.
Result and scope: Hurlbert's ordering conjecture (Kirsch-Sibley-Sprangel Conjecture 6.3; Hurlbert 1990; the Chung-Diaconis-Graham 1992 belief) is false at n = 4: an explicit Euler tour of the clustered overlap graph O(4) is realized by no cyclic word over any linearly ordered alphabet
Complete proof and verification sources: An Euler tour of the full permutation overlap graph that no cyclic word realizes: a refutation of Hurlbert's ordering conjecture for universal cycles of permutations · PDF.
The paper page includes the supplementary proof-source JSON attachment and extract_sources.py, which reconstruct the archived proof and verification sources. The linked paper gives the complete rigorous argument and specifies exactly which statements are formalized.
This is an AI-assisted research preprint. Internal review is not external journal peer review; bounded prior-art searches do not certify worldwide priority. See the paper for the source, interpretation, formalization, and trust limitations.