Tight bounds on the maximum size of a set of permutations with bounded VC-dimension
From MaRDI portal
Publication:439058
DOI10.1016/j.jcta.2012.04.004zbMath1245.05005arXiv1104.5007MaRDI QIDQ439058
Publication date: 1 August 2012
Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1104.5007
set of permutations; VC-dimension; permutation pattern; inverse Ackermann function; Davenport; Schinzel sequence
05A05: Permutations, words, matrices
Related Items
A generalization of the K\H{o}v\'{a}ri-S\'{o}s-Tur\'{a}n theorem, Unnamed Item, On the zone of a circle in an arrangement of lines, On the zone of a circle in an arrangement of lines, Improved enumeration of simple topological graphs, Almost all permutation matrices have bounded saturation functions, Forbidden formations in multidimensional 0-1 matrices, Linear bounds on matrix extremal functions using visibility hypergraphs, A relationship between generalized Davenport-Schinzel sequences and interval chains, Three Generalizations of Davenport--Schinzel Sequences
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Degrees of nonlinearity in forbidden 0-1 matrix problems
- Generalized Davenport-Schinzel sequences and their 0-1 matrix counterparts
- Excluded permutation matrices and the Stanley-Wilf conjecture
- Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences
- On constants in the Füredi-Hajnal and the Stanley-Wilf conjecture
- Extremal functions of forbidden double permutation matrices
- Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes
- Davenport-Schinzel theory of matrices
- Generalized Davenport-Schinzel sequences
- The maximum number of unit distances in a convex \(n\)-gon
- A near-linear algorithm for the planar segment-center problem
- Forbidden paths and cycles in ordered graphs and matrices
- On 0-1 matrices and small excluded submatrices
- Improved bounds and new techniques for Davenport--Schinzel sequences and their generalizations
- An Extremal Problem on Sparse 0-1 Matrices
- A Combinatorial Problem Connected with Differential Equations
- VC-dimension of sets of permutations
