Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
sequence; Davenport-Schinzel sequence; length; upper bound
sequence; Davenport-Schinzel sequence; length; upper bound
Summary:
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_1a_2...a_m$ of integers such that 1) $1 \leq a_i \leq n$, 2) $a_i=a_j, i\not =j$ implies $|i-j|\geq 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(n2^{O(\alpha (n)^{|u|-4})}). $$ Here $|u|$ is the length of $u$ and $\alpha (n)$ is the inverse to the Ackermann function and goes to infinity very slowly. This result extends the estimates in [S] and [ASS] which treat the case $u=abababa\ldots $ and is achieved by similar methods.
References:
[AKV] Adamec R., Klazar M., Valtr P.: Generalized Davenport-Schinzel sequences with linear upper bound. Topological, algebraical and combinatorial structures (ed. J.Nešetřil), North Holland, to appear. MR 1189846 | Zbl 0768.05007
[ASS] Agarwal P., Sharir M., Shor P.: Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences. J. of Comb. Th. A 52 (1989), 228-274. MR 1022320 | Zbl 0697.05003
[DS] Davenport H., Schinzel M.: A combinatorial problem connected with differential equations I and II. Amer. J. Math. 87 (1965), 684-689 and Acta Arithmetica 17 (1971), 363-372. MR 0190010
[ES] Erdös P., Szekeres G.: A combinatorial problem in geometry. Compocito Math. 2 (1935), 464-470.
[FH] Füredi Z., Hajnal P.: Davenport-Schinzel theory of matrices. Discrete Math. (1991). MR 1171777
[HS] 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
[K] Komjáth P.: A simplified construction of nonlinear Davenport-Schinzel sequences. J. of Comb. Th. A 49 (1988), 262-267. MR 0964387
[Kl] Klazar M.: A linear upper bound in extremal theory of sequences. to appear in J. of Comb. Th. A. MR 1297182 | Zbl 0808.05096
[S] Sharir M.: Almost linear upper bounds on the length of generalized Davenport-Schinzel sequences. Combinatorica 7 (1987), 131-143. MR 0905160
[Sz] Szemerédi E.: On a problem by Davenport and Schinzel. Acta Arithm. 15 (1974), 213-224. MR 0335463
[WS] Wiernick A., Sharir M.: Planar realization of nonlinear Davenport-Schinzel sequences by segments. Discrete Comp. Geom. 3 (1988), 15-47. MR 0918177
Search
Partner of
