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.
Containing all permutations
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
Numerous versions of the question "what is the shortest object containing all permutations of a given length?" have been asked over the past fifty years: by Karp (via Knuth) in 1972; by Chung, Diaconis, and Graham in 1992; by Ashlock and Tillotson in 1993; and by Arratia in 1999. The large variety of questions of this form, which have previously been considered in isolation, stands in stark contrast to the dearth of answers. We survey and synthesize these questions and their partial answers, introduce infinitely more related questions, and then establish an improved upper bound for one of these questions.
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.