Two results on a partial ordering of finite sequences
Klazar, Martin
Commentationes Mathematicae Universitatis Carolinae, Tome 34 (1993), p. 697-705 / Harvested from Czech Digital Mathematics Library
Access to full text
Full (PDF)

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.

Publié le : 1993-01-01
Classification:  05D99,  06A07 
@article{118626,
     author = {Martin Klazar},
     title = {Two results on a partial ordering of finite sequences},
     journal = {Commentationes Mathematicae Universitatis Carolinae},
     volume = {34},
     year = {1993},
     pages = {697-705},
     zbl = {0789.05090},
     mrnumber = {1263798},
     language = {en},
     url = {http://dml.mathdoc.fr/item/118626}
}

Klazar, Martin. Two results on a partial ordering of finite sequences. Commentationes Mathematicae Universitatis Carolinae, Tome 34 (1993) pp. 697-705. http://gdmltest.u-ga.fr/item/118626/

Adamec R.; Klazar M.; Valtr P. Generalized Davenport-Schinzel sequences with linear upper bound, Discrete Math. 108 (1992), 219-229. (1992) | MR 1189846 | Zbl 0768.05007

Agarwal P.K.; Sharir M.; Shor P. Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences, J. Comb. Theory A 52 (1989), 228-274. (1989) | MR 1022320 | Zbl 0697.05003

Davenport H.; Schinzel A. A combinatorial problem connected with differential equations, Amer. J. Math. 87 (1965), 684-689. (1965) | MR 0190010 | Zbl 0132.00601

Davenport H. A combinatorial problem connected with differential equations II, Acta Arith. 17 (1971), 363-372. (1971) | MR 0285401 | Zbl 0216.30204

Graphs and Orders, (I. Rival, ed.) D. Reidel Publishing Company, Dordrecht, 1985. | MR 0818494

Hart S.; Sharir M. Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes, Combinatorica 6 (1986), 151-177. (1986) | MR 0875839 | Zbl 0636.05003

Higman H. Orderi divisibility in abstract algebras, Proc. London Math. Society 2 (1952), 326-336. (1952) | MR 0049867

Klazar M. A general upper bound in Extremal theory of sequences, Comment. Math. Univ. Carolinae 33 (1992), 737-747. (1992) | MR 1240196 | Zbl 0781.05049

Klazar M.; Valtr P. Linear sequences, submitted.

Milner E.C. Basic wqo and bqo theory, in 5. | Zbl 0573.06002

Nash-Williams C.St.J.A. On well-quasi-ordering finite trees, Math. Proc. Cambridge Philos. Soc. 59 (1963), 833-835. (1963) | MR 0153601 | Zbl 0122.25001

Robertson N.; Seymour P. Graph minors-a survey, Surveys in Combinatorics (Glasgow 1985) (I. Anderson, ed.), Cambridge Univ. Press, 153-171. | MR 0822774 | Zbl 0568.05025

Sharir M. Almost linear upper bounds on the length of general Davenport-Schinzel sequences, Combinatorica 7 (1987), 131-143. (1987) | MR 0905160 | Zbl 0636.05004

Szemerédi E. On a problem by Davenport and Schinzel, Acta Arith. 25 (1974), 213-224. (1974) | MR 0335463

Wiernik A.; Sharir M. Planar realization of nonlinear Davenport-Schinzel, Discrete Comput. Geometry 3 (1988), 15-47. (1988) | MR 0918177