Defines superpermutation matrices, reduces their row/column minimization to a universal word problem for quotient classes in S_n, and proves the ratio of the resulting upper and lower bounds tends to 2 as n grows.
Universal cycles for permutations
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
A universal cycle for permutations is a word of length n! such that each of the n! possible relative orders of n distinct integers occurs as a cyclic interval of the word. We show how to construct such a universal cycle in which only n+1 distinct integers are used. This is best possible and proves a conjecture of Chung, Diaconis and Graham.
fields
math.CO 1years
2019 1verdicts
CONDITIONAL 1representative citing papers
citing papers explorer
-
Superpermutation matrices
Defines superpermutation matrices, reduces their row/column minimization to a universal word problem for quotient classes in S_n, and proves the ratio of the resulting upper and lower bounds tends to 2 as n grows.