Klazar, Martin A general upper bound in extremal theory of sequences. (English) Zbl 0781.05049 Commentat. Math. Univ. Carol. 33, No. 4, 737-746 (1992). A very general upper bound is given for the maximal length of sequences from \(n\) letters where any two occurrences of the same letter are separated by at least \(k-1\) other letters and a given type \(u\) of length \(s+4\) of \(k\) letters is excluded. The bound is \(n2^{O(\alpha(n)^ s)}\) where \(\alpha(n)\) is the functional inverse of the Ackermann function. This extends earlier results of Hart, Sharir, the author, and others. Reviewer: P.Komjáth (Budapest) Cited in 23 Documents MSC: 05D99 Extremal combinatorics 68R15 Combinatorics on words Keywords:extremal theory; Davenport-Schinzel sequences; upper bound; maximal length PDFBibTeX XMLCite \textit{M. Klazar}, Commentat. Math. Univ. Carol. 33, No. 4, 737--746 (1992; Zbl 0781.05049) Full Text: EuDML