Lower bounds for superpatterns and universal sequences

2020/04/06 by Zachary Chroman, Matthew Kwan, Chroman, Zachary +3
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO

paper · pdf · doi:10.48550/arxiv.2004.02375

12 pages

arxiv created 2021/02/02 · arxiv updated 2021/02/03

Abstract

A permutation σ∈ S_n is said to be k-universal or a k-superpattern if for every π∈ S_k, there is a subsequence of σ that is order-isomorphic to π. A simple counting argument shows that σ can be a k-superpattern only if n≥ (1/e²+o(1))k², and Arratia conjectured that this lower bound is best-possible. Disproving Arratia's conjecture, we improve the trivial bound by a small constant factor. We accomplish this by designing an efficient encoding scheme for the patterns that appear in σ. This approach is quite flexible and is applicable to other universality-type problems; for example, we also improve a bound by Engen and Vatter on a problem concerning (k+1)-ary sequences which contain all k-permutations.

Related

• An asymptotically tight lower bound for superpatterns with small alphabets
• Some Results on Superpatterns for Preferential Arrangements
• Skip Letters for Short Supersequence of All Permutations
• Improved Algorithm for Permutation Testing
• Improved Bounds for Testing Forbidden Order Patterns