Superpermutation matrices

2019/08/13 by Guillaume Dumas, Dumas, Guillaume
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO

paper · pdf · doi:10.48550/arxiv.1908.04708

18 pages

arxiv created 2019/08/13 · arxiv updated 2019/08/14

Abstract

Superpermutations are words over a finite alphabet containing every permutation as a factor. Finding the minimal length of a superpermutation is still an open problem. In this article, we introduce superpermutations matrices. We establish a link between the minimal size of such a matrix and the minimal length of a universal word for the quotient of the symmetric group S_n by an equivalence relation. We will then give non-trivial bounds on the minimal length of such a word and prove that the limit of their ratio when n approaches infinity is 2.

Related

• Tackling the Minimal Superpermutation Problem
• An asymptotically tight lower bound for superpatterns with small alphabets
• Non-Uniqueness of Minimal Superpermutations
• Longest alternating subsequences of permutations
• Skip Letters for Short Supersequence of All Permutations