Extremal functions for sequences
type: Item
instance of: scholarly article
title: Extremal functions for sequences
zbMATH Open document ID: 0851.05093
DOI: 10.1016/0012-365X(95)00188-3
author: Martin Klazar
published in: Discrete Mathematics
publication date: 1996-11-24T00:00:00Z
review text: This paper deals with a certain kind of finite sequences of symbols having no immediate repetition and with no alternating subsequence of length \(s\). Strong upper and lower bounds on the maximum length of such sequences with \(n\) symbols are well known. In this paper the author discusses some properties of the generalization of this concept and goes on to show that the extremal functions of \(aa\dots abb\dots baa\dots abb\dots b\) grow linearly.
Mathematics Subject Classification ID: 05D99
Mathematics Subject Classification ID: 68R15
zbMATH DE Number: 896000
zbMATH Keywords: finite sequences
zbMATH Keywords: extremal functions
reviewed by: D. V. Chopra
MaRDI profile type: Publication
cites work: Generalized Davenport-Schinzel sequences with linear upper bound
cites work: Q3997899
cites work: Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences
cites work: Q3852212
cites work: A Combinatorial Problem Connected with Differential Equations
cites work: Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes
cites work: Q3137399
cites work: A linear upper bound in extremal theory of sequences
cites work: Q4285969
cites work: Generalized Davenport-Schinzel sequences
cites work: Almost linear upper bounds on the length of general Davenport-Schinzel sequences
cites work: On a problem of Davenport and Schinzel
description: scientific article; zbMATH DE number 896000