Geodesic
Two results on a partial ordering of finite sequences
Commentationes Mathematicae Universitatis Carolinae, Tome 34 (1993) no. 4, pp. 697-705

Voir la notice de l'article provenant de la source Czech Digital Mathematics Library

In the first part of the paper we are concerned about finite sequences (over arbitrary symbols) $u$ for which $Ex(u,n)=O(n)$. The function $Ex(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 $ababa\prec u$ is a (minimal) obstacle to $Ex(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 the above containment of sequences is wqo. It is trivial that it is not but we show that the smaller family of sequences whose alternate graphs contain no $k$-path is well quasiordered by that containment.
Classification : 05D99, 06A07
Keywords: Davenport-Schinzel sequence; extremal problem; linear growth; minimal obstacle to linearity; well quasiordering; alternate graph 
@article{CMUC_1993__34_4_a7,
     author = {Klazar, Martin},
     title = {Two results on a partial ordering of finite sequences},
     journal = {Commentationes Mathematicae Universitatis Carolinae},
     pages = {697--705},
     publisher = {mathdoc},
     volume = {34},
     number = {4},
     year = {1993},
     mrnumber = {1263798},
     zbl = {0789.05090},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/CMUC_1993__34_4_a7/}
}
TY  - JOUR
AU  - Klazar, Martin
TI  - Two results on a partial ordering of finite sequences
JO  - Commentationes Mathematicae Universitatis Carolinae
PY  - 1993
SP  - 697
EP  - 705
VL  - 34
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/CMUC_1993__34_4_a7/
LA  - en
ID  - CMUC_1993__34_4_a7
ER  - 
%0 Journal Article
%A Klazar, Martin
%T Two results on a partial ordering of finite sequences
%J Commentationes Mathematicae Universitatis Carolinae
%D 1993
%P 697-705
%V 34
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/CMUC_1993__34_4_a7/
%G en
%F CMUC_1993__34_4_a7
Klazar, Martin. Two results on a partial ordering of finite sequences. Commentationes Mathematicae Universitatis Carolinae, Tome 34 (1993) no. 4, pp. 697-705. http://geodesic.mathdoc.fr/item/CMUC_1993__34_4_a7/