Three Generalizations of Davenport--Schinzel Sequences
From MaRDI portal
Publication:3452162
DOI10.1137/140968574zbMath1329.05010arXiv1401.5709OpenAlexW2151003636MaRDI QIDQ3452162
Publication date: 18 November 2015
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1401.5709
Exact enumeration problems, generating functions (05A15) Combinatorics in computer science (68R05) Combinatorics on words (68R15) Permutations, words, matrices (05A05)
Related Items (4)
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 ⋮ Lower bounds on Davenport-Schinzel sequences via rectangular Zarankiewicz matrices
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Bounding sequence extremal functions with formations
- Degrees of nonlinearity in forbidden 0-1 matrix problems
- Tight bounds on the maximum size of a set of permutations with bounded VC-dimension
- Generalized Davenport-Schinzel sequences and their 0-1 matrix counterparts
- Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences
- 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 the deque conjecture for the splay algorithm
- Davenport-Schinzel theory of matrices
- Generalized Davenport-Schinzel sequences with linear upper bound
- Generalized Davenport-Schinzel sequences
- Extremal functions for sequences
- A note on sequences and subsequences
- On 0-1 matrices and small excluded submatrices
- Origins of Nonlinearity in Davenport–Schinzel Sequences
- k-Quasi-Planar Graphs
- Improved bounds and new techniques for Davenport--Schinzel sequences and their generalizations
- Efficiency of a Good But Not Linear Set Union Algorithm
- Sharp bounds on Davenport-Schinzel sequences of every order
- The Number of Edges in $k$-Quasi-planar Graphs
- A Combinatorial Problem Connected with Differential Equations
- Sharp Bounds on Formation-free Sequences
- On the structure and composition of forbidden sequences, with geometric applications
This page was built for publication: Three Generalizations of Davenport--Schinzel Sequences
