# A general upper bound in extremal theory of sequences

Commentationes Mathematicae Universitatis Carolinae (1992)

- Volume: 33, Issue: 4, page 737-746
- ISSN: 0010-2628

## Access Full Article

top## Abstract

top## How to cite

topKlazar, Martin. "A general upper bound in extremal theory of sequences." Commentationes Mathematicae Universitatis Carolinae 33.4 (1992): 737-746. <http://eudml.org/doc/247383>.

@article{Klazar1992,

abstract = {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 \le a_i \le n$, 2) $a_i=a_j, i\ne j$ implies $|i-j|\ge 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.},

author = {Klazar, Martin},

journal = {Commentationes Mathematicae Universitatis Carolinae},

keywords = {sequence; Davenport-Schinzel sequence; length; upper bound; extremal theory; Davenport-Schinzel sequences; upper bound; maximal length},

language = {eng},

number = {4},

pages = {737-746},

publisher = {Charles University in Prague, Faculty of Mathematics and Physics},

title = {A general upper bound in extremal theory of sequences},

url = {http://eudml.org/doc/247383},

volume = {33},

year = {1992},

}

TY - JOUR

AU - Klazar, Martin

TI - A general upper bound in extremal theory of sequences

JO - Commentationes Mathematicae Universitatis Carolinae

PY - 1992

PB - Charles University in Prague, Faculty of Mathematics and Physics

VL - 33

IS - 4

SP - 737

EP - 746

AB - 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 \le a_i \le n$, 2) $a_i=a_j, i\ne j$ implies $|i-j|\ge 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.

LA - eng

KW - sequence; Davenport-Schinzel sequence; length; upper bound; extremal theory; Davenport-Schinzel sequences; upper bound; maximal length

UR - http://eudml.org/doc/247383

ER -

## References

top- 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. Zbl0768.05007MR1189846
- 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) Zbl0697.05003MR1022320
- 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) MR0190010
- 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) MR1171777
- Hart S., Sharir M., Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes, Combinatorica 6 (1986), 151-177. (1986) Zbl0636.05003MR0875839
- Komjáth P., A simplified construction of nonlinear Davenport-Schinzel sequences, J. of Comb. Th. A 49 (1988), 262-267. (1988) MR0964387
- Klazar M., A linear upper bound in extremal theory of sequences, to appear in J. of Comb. Th. A. Zbl0808.05096MR1297182
- Sharir M., Almost linear upper bounds on the length of generalized Davenport-Schinzel sequences, Combinatorica 7 (1987), 131-143. (1987) MR0905160
- Szemerédi E., On a problem by Davenport and Schinzel, Acta Arithm. 15 (1974), 213-224. (1974) MR0335463
- Wiernick A., Sharir M., Planar realization of nonlinear Davenport-Schinzel sequences by segments, Discrete Comp. Geom. 3 (1988), 15-47. (1988) MR0918177

## Citations in EuDML Documents

top## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.