A general upper bound in extremal theory of sequences
Klazar, Martin
Commentationes Mathematicae Universitatis Carolinae, Tome 33 (1992), p. 737-746 / Harvested from Czech Digital Mathematics Library
Access to full text
Full (PDF)

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.

Publié le : 1992-01-01
Classification:  05D99,  68R15 
@article{118546,
     author = {Martin Klazar},
     title = {A general upper bound in extremal theory of sequences},
     journal = {Commentationes Mathematicae Universitatis Carolinae},
     volume = {33},
     year = {1992},
     pages = {737-746},
     zbl = {0781.05049},
     mrnumber = {1240196},
     language = {en},
     url = {http://dml.mathdoc.fr/item/118546}
}

Klazar, Martin. A general upper bound in extremal theory of sequences. Commentationes Mathematicae Universitatis Carolinae, Tome 33 (1992) pp. 737-746. http://gdmltest.u-ga.fr/item/118546/

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

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. (1989) | MR 1022320 | Zbl 0697.05003

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. (1971) | MR 0190010

Erdös P.; Szekeres G. A combinatorial problem in geometry, Compocito Math. 2 (1935), 464-470. (1935)

Füredi Z.; Hajnal P. Davenport-Schinzel theory of matrices, Discrete Math. (1991). (1991) | MR 1171777

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

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

Klazar M. A linear upper bound in extremal theory of sequences, to appear in J. of Comb. Th. A. | MR 1297182 | Zbl 0808.05096

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

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

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