| Title:
|
A general upper bound in extremal theory of sequences (English) |
| Author:
|
Klazar, Martin |
| Language:
|
English |
| Journal:
|
Commentationes Mathematicae Universitatis Carolinae |
| ISSN:
|
0010-2628 (print) |
| ISSN:
|
1213-7243 (online) |
| Volume:
|
33 |
| Issue:
|
4 |
| Year:
|
1992 |
| Pages:
|
737-746 |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
sequence |
| Keyword:
|
Davenport-Schinzel sequence |
| Keyword:
|
length |
| Keyword:
|
upper bound |
| MSC:
|
05D99 |
| MSC:
|
68R15 |
| idZBL:
|
Zbl 0781.05049 |
| idMR:
|
MR1240196 |
| . |
| Date available:
|
2009-01-08T18:00:22Z |
| Last updated:
|
2012-04-30 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/118546 |
| . |
| Reference:
|
[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. Zbl 0768.05007, MR 1189846 |
| Reference:
|
[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. Zbl 0697.05003, MR 1022320 |
| Reference:
|
[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 |
| Reference:
|
[ES] Erdös P., Szekeres G.: A combinatorial problem in geometry.Compocito Math. 2 (1935), 464-470. |
| Reference:
|
[FH] Füredi Z., Hajnal P.: Davenport-Schinzel theory of matrices.Discrete Math. (1991). MR 1171777 |
| Reference:
|
[HS] Hart S., Sharir M.: Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes.Combinatorica 6 (1986), 151-177. Zbl 0636.05003, MR 0875839 |
| Reference:
|
[K] Komjáth P.: A simplified construction of nonlinear Davenport-Schinzel sequences.J. of Comb. Th. A 49 (1988), 262-267. MR 0964387 |
| Reference:
|
[Kl] Klazar M.: A linear upper bound in extremal theory of sequences.to appear in J. of Comb. Th. A. Zbl 0808.05096, MR 1297182 |
| Reference:
|
[S] Sharir M.: Almost linear upper bounds on the length of generalized Davenport-Schinzel sequences.Combinatorica 7 (1987), 131-143. MR 0905160 |
| Reference:
|
[Sz] Szemerédi E.: On a problem by Davenport and Schinzel.Acta Arithm. 15 (1974), 213-224. MR 0335463 |
| Reference:
|
[WS] Wiernick A., Sharir M.: Planar realization of nonlinear Davenport-Schinzel sequences by segments.Discrete Comp. Geom. 3 (1988), 15-47. MR 0918177 |
| . |
