Generalized Davenport-Schinzel sequences and their 0-1 matrix counterparts
From MaRDI portal
Publication:543917
DOI10.1016/j.jcta.2011.02.011zbMath1227.68087OpenAlexW2021551335MaRDI QIDQ543917
Publication date: 17 June 2011
Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcta.2011.02.011
Related Items (15)
An exact characterization of saturation for permutation matrices ⋮ Almost all permutation matrices have bounded saturation functions ⋮ Greedy Is an Almost Optimal Deque ⋮ Three Generalizations of Davenport--Schinzel Sequences ⋮ k-Quasi-Planar Graphs ⋮ Forbidden formations in multidimensional 0-1 matrices ⋮ Bounds on parameters of minimally nonlinear patterns ⋮ Degrees of nonlinearity in forbidden 0-1 matrix problems ⋮ New bounds on the maximum number of edges in \(k\)-quasi-planar graphs ⋮ Tight bounds on the maximum size of a set of permutations with bounded VC-dimension ⋮ On the zone of a circle in an arrangement of lines ⋮ On the zone of a circle in an arrangement of lines ⋮ Pattern-avoiding \(( 0 , 1 )\)-matrices and bases of permutation matrices ⋮ Lower bounds on Davenport-Schinzel sequences via rectangular Zarankiewicz matrices ⋮ Unnamed Item
Cites Work
- Degrees of nonlinearity in forbidden 0-1 matrix problems
- Excluded permutation matrices and the Stanley-Wilf conjecture
- Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences
- On linear forbidden submatrices
- Linear bound on extremal functions of some forbidden patterns in 0-1 matrices
- Extremal functions of forbidden double permutation matrices
- Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes
- Almost linear upper bounds on the length of general Davenport-Schinzel sequences
- Improved lower bounds on the length of Davenport-Schinzel sequences
- A simplified construction of nonlinear Davenport-Schinzel sequences
- 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
- Weak ε-nets and interval chains
- Improved bounds and new techniques for Davenport--Schinzel sequences and their generalizations
- On a problem of Davenport and Schinzel
- A Combinatorial Problem Connected with Differential Equations
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Generalized Davenport-Schinzel sequences and their 0-1 matrix counterparts
