Generalized Davenport-Schinzel sequences with linear upper bound

DOI10.1016/0012-365X(92)90677-8zbMath0768.05007WikidataQ126529479 ScholiaQ126529479MaRDI QIDQ1201254

Pavel Valtr, Radek Adamec, Martin Klazar

Publication date: 17 January 1993

Published in: Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

forbidden patternmaximum lengthDavenport-Schinzel sequence

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Combinatorics on words (68R15) Enumerative combinatorics (05A99) Special sequences and polynomials (11B83) Applications of graph theory to circuits and networks (94C15)

Related Items (10)

A linear upper bound in extremal theory of sequences ⋮ Generalized Davenport-Schinzel sequences ⋮ Three Generalizations of Davenport--Schinzel Sequences ⋮ Combinatorial aspects of Davenport-Schinzel sequences ⋮ Extremal functions for sequences ⋮ Degrees of nonlinearity in forbidden 0-1 matrix problems ⋮ Turán problems for edge-ordered graphs ⋮ On the zone of a circle in an arrangement of lines ⋮ Generalized Davenport-Schinzel sequences and their 0-1 matrix counterparts ⋮ Extremal problems for colored trees and Davenport-Schinzel sequences

Cites Work

• Unnamed Item
• Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes
• Almost linear upper bounds on the length of general Davenport-Schinzel sequences
• Planar realizations of nonlinear Davenport-Schinzel sequences by segments
• A simplified construction of nonlinear Davenport-Schinzel sequences
• On a problem of Davenport and Schinzel
• Efficiency of a Good But Not Linear Set Union Algorithm
• A Combinatorial Problem Connected with Differential Equations
• A combinatorial problem connected with differential equations II

This page was built for publication: Generalized Davenport-Schinzel sequences with linear upper bound