Tight bounds on the maximum size of a set of permutations with bounded VC-dimension

DOI10.1016/j.jcta.2012.04.004zbMath1245.05005arXiv1104.5007OpenAlexW1979382580MaRDI QIDQ439058

Josef Cibulka, Jan Kynčl

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

zbMATH Keywords

set of permutationsVC-dimensionpermutation patterninverse Ackermann functionDavenportSchinzel sequence

Mathematics Subject Classification ID

Permutations, words, matrices (05A05)

Related Items (10)

Almost all permutation matrices have bounded saturation functions ⋮ Three Generalizations of Davenport--Schinzel Sequences ⋮ A generalization of the K\H{o}v\'{a}ri-S\'{o}s-Tur\'{a}n theorem ⋮ Improved enumeration of simple topological graphs ⋮ Forbidden formations in multidimensional 0-1 matrices ⋮ Unnamed Item ⋮ On the zone of a circle in an arrangement of lines ⋮ On the zone of a circle in an arrangement of lines ⋮ Linear bounds on matrix extremal functions using visibility hypergraphs ⋮ A relationship between generalized Davenport-Schinzel sequences and interval chains

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

This page was built for publication: Tight bounds on the maximum size of a set of permutations with bounded VC-dimension