×

A general upper bound in extremal theory of sequences. (English) Zbl 0781.05049

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.

MSC:

05D99 Extremal combinatorics
68R15 Combinatorics on words
PDFBibTeX XMLCite
Full Text: EuDML