Geodesic
A general upper bound in extremal theory of sequences
Commentationes Mathematicae Universitatis Carolinae, Tome 33 (1992) no. 4, pp. 737-746 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
Classification : 05D99, 68R15
Keywords: sequence; Davenport-Schinzel sequence; length; upper bound 
@article{CMUC_1992_33_4_a19,
     author = {Klazar, Martin},
     title = {A general upper bound in extremal theory of sequences},
     journal = {Commentationes Mathematicae Universitatis Carolinae},
     pages = {737--746},
     year = {1992},
     volume = {33},
     number = {4},
     mrnumber = {1240196},
     zbl = {0781.05049},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/CMUC_1992_33_4_a19/}
}
TY  - JOUR
AU  - Klazar, Martin
TI  - A general upper bound in extremal theory of sequences
JO  - Commentationes Mathematicae Universitatis Carolinae
PY  - 1992
SP  - 737
EP  - 746
VL  - 33
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/CMUC_1992_33_4_a19/
LA  - en
ID  - CMUC_1992_33_4_a19
ER  - 
%0 Journal Article
%A Klazar, Martin
%T A general upper bound in extremal theory of sequences
%J Commentationes Mathematicae Universitatis Carolinae
%D 1992
%P 737-746
%V 33
%N 4
%U http://geodesic.mathdoc.fr/item/CMUC_1992_33_4_a19/
%G en
%F CMUC_1992_33_4_a19
Klazar, Martin. A general upper bound in extremal theory of sequences. Commentationes Mathematicae Universitatis Carolinae, Tome 33 (1992) no. 4, pp. 737-746. http://geodesic.mathdoc.fr/item/CMUC_1992_33_4_a19/

[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 | Zbl

[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 | Zbl

[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

[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

[HS] Hart S., Sharir M.: Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes. Combinatorica 6 (1986), 151-177. | MR | Zbl

[K] Komjáth P.: A simplified construction of nonlinear Davenport-Schinzel sequences. J. of Comb. Th. A 49 (1988), 262-267. | MR

[Kl] Klazar M.: A linear upper bound in extremal theory of sequences. to appear in J. of Comb. Th. A. | MR | Zbl

[S] Sharir M.: Almost linear upper bounds on the length of generalized Davenport-Schinzel sequences. Combinatorica 7 (1987), 131-143. | MR

[Sz] Szemerédi E.: On a problem by Davenport and Schinzel. Acta Arithm. 15 (1974), 213-224. | MR

[WS] Wiernick A., Sharir M.: Planar realization of nonlinear Davenport-Schinzel sequences by segments. Discrete Comp. Geom. 3 (1988), 15-47. | MR