Almost all permutation matrices have bounded saturation functions
From MaRDI portal
Publication:831345
DOI10.37236/10124zbMath1464.05028arXiv2012.14150OpenAlexW3157465197MaRDI QIDQ831345
Publication date: 11 May 2021
Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2012.14150
Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Permutations, words, matrices (05A05) Positive matrices and their generalizations; cones of matrices (15B48)
Related Items (3)
An exact characterization of saturation for permutation matrices ⋮ Saturation of Multidimensional 0-1 Matrices ⋮ Saturation of Ordered Graphs
Cites Work
- Unnamed Item
- On minimum saturated matrices
- Saturating Sperner families
- Degrees of nonlinearity in forbidden 0-1 matrix problems
- Extremal functions of excluded tensor products of permutation matrices
- Tight bounds on the maximum size of a set of permutations with bounded VC-dimension
- Generalized Davenport-Schinzel sequences and their 0-1 matrix counterparts
- Excluded permutation matrices and the Stanley-Wilf conjecture
- On linear forbidden submatrices
- Linear bound on extremal functions of some forbidden patterns in 0-1 matrices
- Extremal functions of forbidden double permutation matrices
- \(L_ 1\) shortest paths among polygonal obstacles in the plane
- Davenport-Schinzel theory of matrices
- Bounds on parameters of minimally nonlinear patterns
- Lower bounds on Davenport-Schinzel sequences via rectangular Zarankiewicz matrices
- The maximum number of unit distances in a convex \(n\)-gon
- The saturation number of induced subposets of the Boolean lattice
- Saturation problems in the Ramsey theory of graphs, posets and point sets
- Constructing sparse Davenport-Schinzel sequences
- Sharper bounds and structural results for minimally nonlinear 0-1 matrices
- Extremal functions of forbidden multidimensional matrices
- Forbidden formations in multidimensional 0-1 matrices
- Forbidden paths and cycles in ordered graphs and matrices
- Linear bounds on matrix extremal functions using visibility hypergraphs
- On 0-1 matrices and small excluded submatrices
- Extensions of the linear bound in the Füredi-Hajnal conjecture
- Improved bounds and new techniques for Davenport--Schinzel sequences and their generalizations
- An Extremal Problem on Sparse 0-1 Matrices
- Better upper bounds on the Füredi-Hajnal limits of permutations
- Cycle-Saturated Graphs with Minimum Number of Edges
- A Problem in Graph Theory
- Forbidden Hypermatrices Imply General Bounds on Induced Forbidden Subposet Problems
- On a problem of K. Zarankiewicz
- On the Turán number of ordered forests
This page was built for publication: Almost all permutation matrices have bounded saturation functions
