An exact characterization of saturation for permutation matrices

DOI10.5070/C63160430MaRDI QIDQ5886259zbMATH OpenFDO

Authors Benjamin Aram Berendsohn

Publication date 31 March 2023

Published in Combinatorial Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2105.02210

zbMATH Keywords

forbidden submatricessaturation

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Extremal set theory (05D05)

Recommendations

• On asymptotic dimension of groups
• Box spaces, group extensions and coarse embeddings into Hilbert space
• Asymptotic dimension of discrete groups
• Dimension of elementary amenable groups
• A Hurewicz-type theorem for asymptotic dimension and applications to geometric group theory

Cites work

• Almost all permutation matrices have bounded saturation functions
• An Extremal Problem on Sparse 0-1 Matrices
• Davenport-Schinzel theory of matrices
• Degrees of nonlinearity in forbidden 0-1 matrix problems
• Excluded permutation matrices and the Stanley-Wilf conjecture
• Extremal functions of forbidden double permutation matrices
• Forbidden paths and cycles in ordered graphs and matrices
• Forbidden subposet problems in the grid
• Generalized Davenport-Schinzel sequences and their 0-1 matrix counterparts
• scientific article; zbMATH DE number 3492580 (Why is no real title available?)
• scientific article; zbMATH DE number 1504588 (Why is no real title available?)
• scientific article; zbMATH DE number 6297801 (Why is no real title available?)
• Linear bound on extremal functions of some forbidden patterns in 0-1 matrices
• Norm-graphs: Variations and applications
• On 0-1 matrices and small excluded submatrices
• On linear forbidden submatrices
• Pattern-avoiding \(( 0 , 1 )\)-matrices and bases of permutation matrices
• Permutation classes
• Saturation problems about forbidden 0-1 submatrices
• Self-adjusting binary search trees: what makes them tick?
• Simple permutations: Decidability and unavoidable substructures
• Small permutation classes
• The maximum number of unit distances in a convex n-gon

Cited in

(8)

• On minimum saturated matrices
• Saturation problems about forbidden 0-1 submatrices
• Saturation of Multidimensional 0-1 Matrices
• Sufficient conditions for permutation equivalence to a WHS-matrix
• Saturation of Ordered Graphs
• The rotation distance of brooms
• Sequence saturation
• Almost all permutation matrices have bounded saturation functions

This page was built for publication: An exact characterization of saturation for permutation matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5886259)