Extremal functions for sequences

DOI10.1016/0012-365X(95)00188-3MaRDI QIDQ1916110zbMATH OpenFDO

Authors Martin Klazar

Publication date 24 November 1996

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365X(95)00188-3

zbMATH Keywords

extremal functionsfinite sequences

Mathematics Subject Classification ID

Extremal combinatorics (05D99) Combinatorics on words (68R15)

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.

Recommendations

• scientific article; zbMATH DE number 427792
• Generalized Davenport-Schinzel sequences
• Generalized Davenport-Schinzel sequences with linear upper bound

Cites work

• A Combinatorial Problem Connected with Differential Equations
• A linear upper bound in extremal theory of sequences
• Almost linear upper bounds on the length of general Davenport-Schinzel sequences
• Generalized Davenport-Schinzel sequences
• Generalized Davenport-Schinzel sequences with linear upper bound
• scientific article; zbMATH DE number 427792 (Why is no real title available?)
• scientific article; zbMATH DE number 3652373 (Why is no real title available?)
• scientific article; zbMATH DE number 49092 (Why is no real title available?)
• scientific article; zbMATH DE number 536973 (Why is no real title available?)
• Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes
• On a problem of Davenport and Schinzel
• Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences

Cited in

(12)

• Combinatorial aspects of Davenport-Schinzel sequences
• Extremal sequences with forbidden sums
• scientific article; zbMATH DE number 427792 (Why is no real title available?)
• Three generalizations of Davenport-Schinzel sequences
• scientific article; zbMATH DE number 3983298 (Why is no real title available?)
• Bounding sequence extremal functions with formations
• scientific article; zbMATH DE number 536973 (Why is no real title available?)
• Further results on minimizing positive integer sequences without duplicate substrings
• Generalized Davenport-Schinzel sequences and their 0-1 matrix counterparts
• Long finite sequences
• Sequence saturation
• Nondecreasing subsequences of t-sequences

This page was built for publication: Extremal functions for sequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1916110)