2021/08/12 by Zach Hunter, Hunter, Zach
Computer Science · Mathematics · #05D99 #Algorithms and Data Compression #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #math.CO #msc:05D99 #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2108.05474
20 pages, comments welcome!
arxiv created 2021/08/12 · openalex publication_date 2021/08/12 · arxiv updated 2021/08/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A permutation σ∈ Sn is a k-superpattern (or k-universal) if it contains each τ∈ Sk as a pattern. This notion of "superpatterns" can be generalized to words on smaller alphabets, and several questions about superpatterns on small alphabets have recently been raised in the survey of Engen and Vatter. One of these questions concerned the length of the shortest k-superpattern on [k+1]. A construction by Miller gave an upper bound of (k2+k)/2, which we show is optimal up to lower-order terms. This implies a weaker version of a conjecture by Eriksson, Eriksson, Linusson and Wastlund. Our results also refute a 40-year-old conjecture of Gupta.