Previous Page 5

Displaying 81 – 88 of 88

Showing per page

Two results on a partial ordering of finite sequences

Martin Klazar (1993)

Commentationes Mathematicae Universitatis Carolinae

In the first part of the paper we are concerned about finite sequences (over arbitrary symbols) u for which E x ( u , n ) = O ( n ) . The function E x ( u , n ) measures the maximum length of finite sequences over n symbols which contain no subsequence of the type u . It follows from the result of Hart and Sharir that the containment a b a b a u is a (minimal) obstacle to E x ( u , n ) = O ( n ) . We show by means of a construction due to Sharir and Wiernik that there is another obstacle to the linear growth. In the second part of the paper we investigate whether...

Currently displaying 81 – 88 of 88

Previous Page 5