Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
Davenport-Schinzel sequence; extremal problem; linear growth; minimal obstacle to linearity; well quasiordering; alternate graph
Davenport-Schinzel sequence; extremal problem; linear growth; minimal obstacle to linearity; well quasiordering; alternate graph
Summary:
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.
References:
[1] Adamec R., Klazar M., Valtr P.: Generalized Davenport-Schinzel sequences with linear upper bound. Discrete Math. 108 (1992), 219-229. MR 1189846 | Zbl 0768.05007
[2] 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. MR 1022320 | Zbl 0697.05003
[3] Davenport H., Schinzel A.: A combinatorial problem connected with differential equations. Amer. J. Math. 87 (1965), 684-689. MR 0190010 | Zbl 0132.00601
[4] Davenport H.: A combinatorial problem connected with differential equations II. Acta Arith. 17 (1971), 363-372. MR 0285401 | Zbl 0216.30204
[5]
Graphs and Orders. (I. Rival, ed.) D. Reidel Publishing Company, Dordrecht, 1985. MR 0818494
[6] Hart S., Sharir M.: Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes. Combinatorica 6 (1986), 151-177. MR 0875839 | Zbl 0636.05003
[7] Higman H.: Orderi divisibility in abstract algebras. Proc. London Math. Society 2 (1952), 326-336. MR 0049867
[8] Klazar M.: A general upper bound in Extremal theory of sequences. Comment. Math. Univ. Carolinae 33 (1992), 737-747. MR 1240196 | Zbl 0781.05049
[9] Klazar M., Valtr P.: Linear sequences. submitted.
[10] Milner E.C.: Basic wqo and bqo theory. in 5. Zbl 0573.06002
[11] Nash-Williams C.St.J.A.: On well-quasi-ordering finite trees. Math. Proc. Cambridge Philos. Soc. 59 (1963), 833-835. MR 0153601 | Zbl 0122.25001
[12] 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
[13] Sharir M.: Almost linear upper bounds on the length of general Davenport-Schinzel sequences. Combinatorica 7 (1987), 131-143. MR 0905160 | Zbl 0636.05004
[14] Szemerédi E.: On a problem by Davenport and Schinzel. Acta Arith. 25 (1974), 213-224. MR 0335463
[15] Wiernik A., Sharir M.: Planar realization of nonlinear Davenport-Schinzel. Discrete Comput. Geometry 3 (1988), 15-47. MR 0918177
Search
Partner of
