ALBERT — All Library Books, journals and Electronic Records Telegrafenberg

Hits per page

hit 1 - 1 | 1 hit

Sorting

Electronic Resource

Improved lower bounds on the length of Davenport-Schinzel sequences (1988)

Sharir, Micha

Springer

Combinatorica 8 (1988), S. 117-124

add to mindlist on the mindlist

Details

ISSN: 1439-6912

Keywords: 05 A 99 ; 05 C 35 ; 68 B 15

Source: Springer Online Journal Archives 1860-2000

Topics: Mathematics

Notes: Abstract We derive lower bounds on the maximal lengthλ s(n) of (n, s) Davenport Schinzel sequences. These bounds have the form λ2s=1(n)=Ω(nαs(n)), whereα(n) is the extremely slowly growing functional inverse of the Ackermann function. These bounds extend the nonlinear lower boundλ 3 (n)=Ω(nα(n)) due to Hart and Sharir [5], and are obtained by an inductive construction based upon the construction given in [5].

Type of Medium: Electronic Resource

URL: http://dx.doi.org/10.1007/BF02122559

Permalink

	Location	Call Number	Expected	Availability

Others were also interested in ...

Paper (German National Licenses)

Fulltext

hit 1 - 1 | 1 hit