Currently displaying 1 – 10 of 10

Showing per page

Order by Relevance | Title | Year of publication

A general upper bound in extremal theory of sequences

Martin Klazar — 1992

Commentationes Mathematicae Universitatis Carolinae

We investigate the extremal function f ( u , n ) which, for a given finite sequence u over k symbols, is defined as the maximum length m of a sequence v = a 1 a 2 . . . a m of integers such that 1) 1 ≤ a i ≤ n , 2) a i = a j , i ≠ j implies | i - j | ≥ k and 3) v contains no subsequence of the type u . We prove that f ( u , n ) is very near to be linear in n for any fixed u of length greater than 4, namely that f ( u , n ) = O ( n 2 O ( α ( n ) | u | - 4 ) ) . Here | u | is the length of u and α ( n ) is the inverse to the Ackermann function and goes to infinity very slowly. This result extends the estimates in [S] and [ASS] which...

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...

Page 1

Download Results (CSV)