Two results on a partial ordering of finite sequences
Commentationes Mathematicae Universitatis Carolinae (1993)
- Volume: 34, Issue: 4, page 697-705
- ISSN: 0010-2628
Access Full Article
top
Abstract
topHow to cite
topKlazar, Martin. "Two results on a partial ordering of finite sequences." Commentationes Mathematicae Universitatis Carolinae 34.4 (1993): 697-705. <http://eudml.org/doc/247489>.
@article{Klazar1993,
abstract = {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.},
author = {Klazar, Martin},
journal = {Commentationes Mathematicae Universitatis Carolinae},
keywords = {Davenport-Schinzel sequence; extremal problem; linear growth; minimal obstacle to linearity; well quasiordering; alternate graph; Davenport-Schinzel sequence; well quasiordering; finite sequences; obstacle; linear growth; alternate graphs},
language = {eng},
number = {4},
pages = {697-705},
publisher = {Charles University in Prague, Faculty of Mathematics and Physics},
title = {Two results on a partial ordering of finite sequences},
url = {http://eudml.org/doc/247489},
volume = {34},
year = {1993},
}
TY - JOUR
AU - Klazar, Martin
TI - Two results on a partial ordering of finite sequences
JO - Commentationes Mathematicae Universitatis Carolinae
PY - 1993
PB - Charles University in Prague, Faculty of Mathematics and Physics
VL - 34
IS - 4
SP - 697
EP - 705
AB - 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.
LA - eng
KW - Davenport-Schinzel sequence; extremal problem; linear growth; minimal obstacle to linearity; well quasiordering; alternate graph; Davenport-Schinzel sequence; well quasiordering; finite sequences; obstacle; linear growth; alternate graphs
UR - http://eudml.org/doc/247489
ER -
References
top- Adamec R., Klazar M., Valtr P., Generalized Davenport-Schinzel sequences with linear upper bound, Discrete Math. 108 (1992), 219-229. (1992) Zbl0768.05007MR1189846
- 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) Zbl0697.05003MR1022320
- Davenport H., Schinzel A., A combinatorial problem connected with differential equations, Amer. J. Math. 87 (1965), 684-689. (1965) Zbl0132.00601MR0190010
- Davenport H., A combinatorial problem connected with differential equations II, Acta Arith. 17 (1971), 363-372. (1971) Zbl0216.30204MR0285401
- Graphs and Orders, (I. Rival, ed.) D. Reidel Publishing Company, Dordrecht, 1985. MR0818494
- Hart S., Sharir M., Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes, Combinatorica 6 (1986), 151-177. (1986) Zbl0636.05003MR0875839
- Higman H., Orderi divisibility in abstract algebras, Proc. London Math. Society 2 (1952), 326-336. (1952) MR0049867
- Klazar M., A general upper bound in Extremal theory of sequences, Comment. Math. Univ. Carolinae 33 (1992), 737-747. (1992) Zbl0781.05049MR1240196
- Klazar M., Valtr P., Linear sequences, submitted.
- Milner E.C., Basic wqo and bqo theory, in 5. Zbl0573.06002
- Nash-Williams C.St.J.A., On well-quasi-ordering finite trees, Math. Proc. Cambridge Philos. Soc. 59 (1963), 833-835. (1963) Zbl0122.25001MR0153601
- Robertson N., Seymour P., Graph minors-a survey, Surveys in Combinatorics (Glasgow 1985) (I. Anderson, ed.), Cambridge Univ. Press, 153-171. Zbl0568.05025MR0822774
- Sharir M., Almost linear upper bounds on the length of general Davenport-Schinzel sequences, Combinatorica 7 (1987), 131-143. (1987) Zbl0636.05004MR0905160
- Szemerédi E., On a problem by Davenport and Schinzel, Acta Arith. 25 (1974), 213-224. (1974) MR0335463
- Wiernik A., Sharir M., Planar realization of nonlinear Davenport-Schinzel, Discrete Comput. Geometry 3 (1988), 15-47. (1988) MR0918177
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.