A general upper bound in extremal theory of sequences

Martin Klazar

Commentationes Mathematicae Universitatis Carolinae (1992)

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

Abstract

top
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 1 a 2 . . . a m of integers such that 1) 1 ≤ a i ≤ n , 2) a i = a j , i ≠ j implies | i - j | ≥ 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 ( n 2 O ( α ( n ) | u | - 4 ) ) . Here | u | is the length of u and α ( 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 = a b a b a b a ... and is achieved by similar methods.

How to cite

top

Klazar, 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
  1. 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
  2. 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
  3. 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
  4. Erdös P., Szekeres G., A combinatorial problem in geometry, Compocito Math. 2 (1935), 464-470. (1935) 
  5. Füredi Z., Hajnal P., Davenport-Schinzel theory of matrices, Discrete Math. (1991). (1991) MR1171777
  6. Hart S., Sharir M., Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes, Combinatorica 6 (1986), 151-177. (1986) Zbl0636.05003MR0875839
  7. Komjáth P., A simplified construction of nonlinear Davenport-Schinzel sequences, J. of Comb. Th. A 49 (1988), 262-267. (1988) MR0964387
  8. Klazar M., A linear upper bound in extremal theory of sequences, to appear in J. of Comb. Th. A. Zbl0808.05096MR1297182
  9. Sharir M., Almost linear upper bounds on the length of generalized Davenport-Schinzel sequences, Combinatorica 7 (1987), 131-143. (1987) MR0905160
  10. Szemerédi E., On a problem by Davenport and Schinzel, Acta Arithm. 15 (1974), 213-224. (1974) MR0335463
  11. Wiernick A., Sharir M., Planar realization of nonlinear Davenport-Schinzel sequences by segments, Discrete Comp. Geom. 3 (1988), 15-47. (1988) MR0918177

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.