Three generalizations of Davenport-Schinzel sequences
From MaRDI portal
Publication:3452162
Abstract: We present new, and mostly sharp, bounds on the maximum length of certain generalizations of Davenport-Schinzel sequences. Among the results are sharp bounds on order- {em double DS} sequences, for all , sharp bounds on sequences avoiding {em catenated permutations} (aka formation free sequences), and new lower bounds on sequences avoiding {em zig-zagging} patterns.
Recommendations
- Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences
- scientific article; zbMATH DE number 1808181
- Sharp bounds on Davenport-Schinzel sequences of every order
- Almost linear upper bounds on the length of general Davenport-Schinzel sequences
- Improved bounds and new techniques for Davenport-Schinzel sequences and their generalizations
Cites work
- scientific article; zbMATH DE number 427792 (Why is no real title available?)
- scientific article; zbMATH DE number 1808181 (Why is no real title available?)
- scientific article; zbMATH DE number 5764839 (Why is no real title available?)
- scientific article; zbMATH DE number 1341912 (Why is no real title available?)
- A Combinatorial Problem Connected with Differential Equations
- A note on sequences and subsequences
- A simplified construction of nonlinear Davenport-Schinzel sequences
- Almost linear upper bounds on the length of general Davenport-Schinzel sequences
- Bounding sequence extremal functions with formations
- Davenport-Schinzel theory of matrices
- Degrees of nonlinearity in forbidden 0-1 matrix problems
- Efficiency of a Good But Not Linear Set Union Algorithm
- Extremal functions for sequences
- Generalized Davenport-Schinzel sequences
- Generalized Davenport-Schinzel sequences and their 0-1 matrix counterparts
- Generalized Davenport-Schinzel sequences with linear upper bound
- Improved bounds and new techniques for Davenport-Schinzel sequences and their generalizations
- Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes
- On 0-1 matrices and small excluded submatrices
- On the deque conjecture for the splay algorithm
- On the structure and composition of forbidden sequences, with geometric applications
- Origins of nonlinearity in Davenport-Schinzel sequences
- Planar realizations of nonlinear Davenport-Schinzel sequences by segments
- Sharp bounds on Davenport-Schinzel sequences of every order
- Sharp bounds on formation-free sequences
- Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences
- The number of edges in \(k\)-quasi-planar graphs
- Tight bounds on the maximum size of a set of permutations with bounded VC-dimension
- \(k\)-quasi-planar graphs
Cited in
(10)- Lower bounds on Davenport-Schinzel sequences via rectangular Zarankiewicz matrices
- Sharp bounds on formation-free sequences
- Constructing sparse Davenport-Schinzel sequences
- On numbers of Davenport-Schinzel sequences
- scientific article; zbMATH DE number 1424289 (Why is no real title available?)
- On the zone of a circle in an arrangement of lines
- scientific article; zbMATH DE number 1808181 (Why is no real title available?)
- On the zone of a circle in an arrangement of lines
- Generalized Davenport-Schinzel sequences with linear upper bound
- A relationship between generalized Davenport-Schinzel sequences and interval chains
This page was built for publication: Three generalizations of Davenport-Schinzel sequences
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3452162)
