Three generalizations of Davenport-Schinzel sequences
From MaRDI portal
Publication:3452162
DOI10.1137/140968574zbMATH Open1329.05010arXiv1401.5709OpenAlexW2151003636MaRDI QIDQ3452162FDOQ3452162
Authors: Seth Pettie 
Publication date: 18 November 2015
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1401.5709
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
Permutations, words, matrices (05A05) Combinatorics in computer science (68R05) Exact enumeration problems, generating functions (05A15) Combinatorics on words (68R15)
Cites Work
- Efficiency of a Good But Not Linear Set Union Algorithm
- Davenport-Schinzel theory of matrices
- The number of edges in \(k\)-quasi-planar graphs
- Title not available (Why is that?)
- Improved bounds and new techniques for Davenport-Schinzel sequences and their generalizations
- Tight bounds on the maximum size of a set of permutations with bounded VC-dimension
- Degrees of nonlinearity in forbidden 0-1 matrix problems
- Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes
- Generalized Davenport-Schinzel sequences with linear upper bound
- Generalized Davenport-Schinzel sequences
- Extremal functions for sequences
- On 0-1 matrices and small excluded submatrices
- Origins of nonlinearity in Davenport-Schinzel sequences
- Title not available (Why is that?)
- Bounding sequence extremal functions with formations
- Title not available (Why is that?)
- A Combinatorial Problem Connected with Differential Equations
- Sharp bounds on formation-free sequences
- On the structure and composition of forbidden sequences, with geometric applications
- Generalized Davenport-Schinzel sequences and their 0-1 matrix counterparts
- Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences
- Planar realizations of nonlinear Davenport-Schinzel sequences by segments
- Sharp bounds on Davenport-Schinzel sequences of every order
- Almost linear upper bounds on the length of general Davenport-Schinzel sequences
- A simplified construction of nonlinear Davenport-Schinzel sequences
- A note on sequences and subsequences
- Title not available (Why is that?)
- On the deque conjecture for the splay algorithm
- \(k\)-quasi-planar graphs
Cited In (10)
- Lower bounds on Davenport-Schinzel sequences via rectangular Zarankiewicz matrices
- Generalized Davenport-Schinzel sequences with linear upper bound
- Title not available (Why is that?)
- Constructing sparse Davenport-Schinzel sequences
- On the zone of a circle in an arrangement of lines
- On the zone of a circle in an arrangement of lines
- Sharp bounds on formation-free sequences
- Title not available (Why is that?)
- On numbers of Davenport-Schinzel sequences
- 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)
