Sequences of formation width and alternation length
Sequence pattern avoidance is a central topic in combinatorics. A sequence contains a sequence if some subsequence of can be changed into by a one-to-one renaming of its letters. If does not contain , then avoids . A widely studied extremal function related to pattern avoidance is , the maximum length of an -letter sequence that avoids and has every consecutive letters pairwise distinct, where is the number of distinct letters in . We bound using the formation width function, , which is the minimum for which there exists such that any concatenation of permutations, each on the same letters, contains . In particular, we identify every sequence such that and contains . The significance of this result lies in its implication that, for every such sequence , we have , where denotes the incredibly slow-growing inverse Ackermann function. We have thus identified the extremal function of many infinite classes of previously unidentified sequences.