Almost linear upper bounds on the length of general Davenport-Schinzel sequences (Q1097885): Difference between revisions

From MaRDI portal
Import240304020342 (talk | contribs)
Set profile property.
Set OpenAlex properties.
 
(One intermediate revision by one other user not shown)
Property / cites work
 
Property / cites work: A combinatorial problem connected with differential equations II / rank
 
Normal rank
Property / cites work
 
Property / cites work: A Combinatorial Problem Connected with Differential Equations / rank
 
Normal rank
Property / cites work
 
Property / cites work: Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes / rank
 
Normal rank
Property / cites work
 
Property / cites work: Some properties of Davenport-Schinzel sequences / rank
 
Normal rank
Property / cites work
 
Property / cites work: Efficiency of a Good But Not Linear Set Union Algorithm / rank
 
Normal rank
Property / full work available at URL
 
Property / full work available at URL: https://doi.org/10.1007/bf02579209 / rank
 
Normal rank
Property / OpenAlex ID
 
Property / OpenAlex ID: W2077909149 / rank
 
Normal rank

Latest revision as of 09:46, 30 July 2024

scientific article
Language Label Description Also known as
English
Almost linear upper bounds on the length of general Davenport-Schinzel sequences
scientific article

    Statements

    Almost linear upper bounds on the length of general Davenport-Schinzel sequences (English)
    0 references
    0 references
    1987
    0 references
    (n,s)-Davenport-Schinzel sequences are sequences that are composed of n symbols, and are such that (i) no two adjacent elements are equal, and (ii) there does not exist a (not necessarily contiguous) alternating subsequence of length \(s+2\) of the form a...b...a...b... for any two distinct symbols a and b. Davenport-Schinzel sequences arise in the computation and analysis of the lower or upper envelope of a set of functions, and are thus a powerful and versatile tool for a variety of problems in combinatorial and computational geometry. This paper establishes almost linear upper bounds on the maximum length \(\lambda_ s(n)\) of (n,s) Davenport-Schinzel sequences. These bounds are of the form \(O(n\alpha (n)^{O(\alpha (n)^{s-3})})\), and they generalize and extend the tight bound \(\Theta\) (n\(\alpha\) (n)) obtained by \textit{S. Hart} and the author [ibid. 6, 151-177 (1986; see above, Zbl 0636.05003)] for the special case \(s=3\) (\(\alpha\) (n) is the extremely slowly growing functional inverse of Ackermann's function), and also improve the upper bound O(n log *n) due to E. Szemeredi (1974). The results of this paper have later been slightly improved by Agarwal, Sharir and Shor (1988), who have shown that \[ \lambda_{2s}(n)=O(n\cdot 2^{O(\alpha (n)^{s-1})}),\quad for\quad s\geq 2,\quad \lambda_{2s+1}(n)=O(n\cdot \alpha (n)^{O(\alpha (n)^{s-1})}),\quad for\quad s\geq 2. \] Moreover, these bounds are almost tight for even s, because \[ \lambda_{2s}(n)=\Omega (n\cdot 2^{\Omega (\alpha (n)^{s- 1})}),\quad for\quad s\geq 2. \]
    0 references
    Davenport-Schinzel sequences
    0 references
    forbidden subsequences
    0 references

    Identifiers