• 検索結果がありません。

A general upper bound in extremal theory of sequences

N/A
N/A
Info
ダウンロード
Protected

Academic year: 2022

シェア "A general upper bound in extremal theory of sequences"

Copied!
1
0
0

読み込み中.... (全文を見る)

今ダウンロードする ( 1 ページ )

全文

(1)

Martin Klazar

A general upper bound in extremal theory of sequences

Comment.Math.Univ.Carolinae 33,4 (1992) 737-746.

Abstract: We investigate the extremal functionf(u, n) which, for a given finite sequence u over k symbols, is defined as the maximum length m of a sequence v = a1a2...am of integers such that 1) 1 ≤ ai ≤ n, 2) ai = aj, i 6= j implies

|i−j| ≥k and 3)v contains no subsequence of the type u. We prove thatf(u, n) is very near to be linear innfor any fixeduof length greater than 4, namely that

f(u, n) =O(n2O(α(n)|u|−4)).

Here |u| is the length ofuandα(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 caseu=abababa... and is achieved by similar methods.

Keywords: sequence, Davenport-Schinzel sequence, length, upper bound AMS Subject Classification: 05D99

1

参照

今ダウンロードする ( PDF - 1 ページ - 65.29 KB )

関連したドキュメント

Daniel ˇSevˇcoviˇc EEJEC >AD=LEH B C>= =JJH=?JHI BH IECK=HO FAHJKH>A@ >A= AGK=JEI MEJD IJHC @=FEC

Keywords: strongly damped beam equation, compact attractor, upper semicon- tinuity of global attractors. AMS Subject Classification:

By considering the upper bound of the amplitude of limit cycles on

In this paper we investigate the same problem to the general Liénard-type system 1.3, and we obtain an explicit upper bound for the amplitude of the unique limit cycle of 1.3 under

ak) be a sequence of elements in Cn

1 This work has been supported partly by the National Natural Science Foundation of China and the Foun- dation of Education Committee of China.... Index(C n ) was first introduced

A sequence T in Zp of length p is called a ϕ-zero sequence ifϕ(T

Bialostocki, Some problems in view of recent developments of the Erd˝ os-Ginzburg-Ziv theorem, Combinatorial number theory, 111–120, de Gruyter, Berlin, 2007.... Dierker, Zero

A general upper bound in extremal theory of sequences

The second aim is to give a brief and clear idea about the techniques developed by Agarwal, Hart, Sharir and Shor for obtaining almost linear upper bounds on f (al s , n) to the

A tight upper bound on the size of the antidictionary of a binary string

A tight upper bound of the size of the antidictionary of a binary string is presented.. And it is shown that the size of the antidictionary of a binary sting is always smaller than

1–2 1 A NOTE ON UPPER BOUND FOR CHROMATIC NUMBER OF A GRAPH L

Excluding the existence of smaller complete subgraphs can further improve the upper bounds for χ(G), as it can be seen from the following result obtained independently by Borodin

An upper bound for the chromatic number of line graphs

The chromatic number of a graph G, denoted by χ(G), is the minimum number of colours required to colour the vertex set of G so that no two adjacent vertices are assigned the