An exact characterization of saturation for permutation matrices

DOI10.5070/C63160430MaRDI QIDQ5886259

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

saturationforbidden submatrices

Mathematics Subject Classification ID

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

Related Items

Saturation of Ordered Graphs, The rotation distance of brooms

Cites Work

• 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
• Almost all permutation matrices have bounded saturation functions
• On linear forbidden submatrices
• Linear bound on extremal functions of some forbidden patterns in 0-1 matrices
• Extremal functions of forbidden double permutation matrices
• Davenport-Schinzel theory of matrices
• Norm-graphs: Variations and applications
• The maximum number of unit distances in a convex \(n\)-gon
• Forbidden subposet problems in the grid
• Pattern-avoiding \(( 0 , 1 )\)-matrices and bases of permutation matrices
• Forbidden paths and cycles in ordered graphs and matrices
• Simple permutations: Decidability and unavoidable substructures
• On 0-1 matrices and small excluded submatrices
• Permutation classes
• Small permutation classes
• Self-Adjusting Binary Search Trees: What Makes Them Tick?
• An Extremal Problem on Sparse 0-1 Matrices
• Saturation Problems about Forbidden 0-1 Submatrices