Generalized Davenport-Schinzel sequences with linear upper bound (Q1201254)

If a sequence of symbols from an \(n\)-letter alphabet has no immediate repetition of the same letter and does not contain a subsequence of the form \(ababa\) then it is a Davenport-Schinzel sequence. The authors generalize this notion in two aspects: 1) No immediate repetition is replaced by \(k\)-regularity (i.e. the number of different symbols among \(k\) consecutive symbols from the sequence is \(k\)). 2) The forbidden pattern \(ababa\) is replaced by an arbitrary pattern. The key problem is to determine the maximum length of such sequences with respect to the size of the alphabet \(n\) and the forbidden pattern \(f\). The main result is that the maximum length is of order \(n\) if and only if the forbidden pattern \(f\) has no subsequence of the form \(ababa\).