2015/02/13 by Jesse Geneson, Geneson, Jesse, Peter M. Tian +2
Computer Science · Engineering · Mathematics · #05D99 #Advanced Combinatorial Mathematics #Algorithms and Data Compression #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #cs.DM #graph theory and CDMA systems #math.CO #msc:05D99
paper · pdf · doi:10.48550/arxiv.1502.04095
20 pages
arxiv created 2015/02/13 · openalex publication_date 2015/02/13 · arxiv updated 2015/02/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Sequence pattern avoidance is a central topic in combinatorics. A sequence s contains a sequence u if some subsequence of s can be changed into u by a one-to-one renaming of its letters. If s does not contain u, then s avoids u. A widely studied extremal function related to pattern avoidance is Ex(u, n), the maximum length of an n-letter sequence that avoids u and has every r consecutive letters pairwise distinct, where r is the number of distinct letters in u. We bound Ex(u, n) using the formation width function, fw(u), which is the minimum s for which there exists r such that any concatenation of s permutations, each on the same r letters, contains u. In particular, we identify every sequence u such that fw(u)=4 and u contains ababa. The significance of this result lies in its implication that, for every such sequence u, we have Ex(u, n) = Θ(n α(n)), where α(n) denotes the incredibly slow-growing inverse Ackermann function. We have thus identified the extremal function of many infinite classes of previously unidentified sequences.