Almost all permutation matrices have bounded saturation functions

DOI10.37236/10124zbMATH Open1464.05028arXiv2012.14150OpenAlexW3157465197MaRDI QIDQ831345FDOQ831345

Authors: Jesse Geneson 

Publication date: 11 May 2021

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: Saturation problems for forbidden graphs have been a popular area of research for many decades, and recently Brualdi and Cao initiated the study of a saturation problem for 0-1 matrices. We say that 0-1 matrix $A$ is saturating for the forbidden 0-1 matrix $P$ if $A$ avoids $P$ but changing any zero to a one in $A$ creates a copy of $P$. Define $sat(n,P)$ to be the minimum possible number of ones in an $nimesn$ 0-1 matrix that is saturating for $P$. Fulek and Keszegh proved that for every 0-1 matrix $P$, either $sat(n,P)=O(1)$ or $sat(n,P)=Theta(n)$. They found two 0-1 matrices $P$ for which $sat(n,P)=O(1)$, as well as infinite families of 0-1 matrices $P$ for which $sat(n,P)=Theta(n)$. Their results imply that $sat(n,P)=Theta(n)$ for almost all $kimesk$ 0-1 matrices $P$. Fulek and Keszegh conjectured that there are many more 0-1 matrices $P$ such that $sat(n,P)=O(1)$ besides the ones they found, and they asked for a characterization of all permutation matrices $P$ such that $sat(n,P)=O(1)$. We affirm their conjecture by proving that almost all $kimesk$ permutation matrices $P$ have $sat(n,P)=O(1)$. We also make progress on the characterization problem, since our proof of the main result exhibits a family of permutation matrices with bounded saturation functions.

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

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• An exact characterization of saturation for permutation matrices
• Saturation of Multidimensional 0-1 Matrices
• Extremal functions of forbidden double permutation matrices
• scientific article; zbMATH DE number 1139703
• Suitable permutations, binary covering arrays, and Paley matrices
• Permutation matrices and beyond: an essay
• Matrices with restricted entries and \(q\)-analogues of permutations
• Permutation matrices, their discrete derivatives and extremal properties
• Permutation (Matrices) and Beyond

zbMATH Keywords

permutation matricesSaturation problems for forbidden graphs

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Positive matrices and their generalizations; cones of matrices (15B48) Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20)

Cites Work

• \(L_ 1\) shortest paths among polygonal obstacles in the plane
• A Problem in Graph Theory
• On a problem of K. Zarankiewicz
• Davenport-Schinzel theory of matrices
• Forbidden paths and cycles in ordered graphs and matrices
• Extensions of the linear bound in the Füredi-Hajnal conjecture
• Title not available (Why is that?)
• Excluded permutation matrices and the Stanley-Wilf conjecture
• On minimum saturated matrices
• Saturating Sperner families
• Cycle-saturated graphs with minimum number of edges
• Improved bounds and new techniques for Davenport-Schinzel sequences and their generalizations
• Tight bounds on the maximum size of a set of permutations with bounded VC-dimension
• The maximum number of unit distances in a convex \(n\)-gon
• Degrees of nonlinearity in forbidden 0-1 matrix problems
• On linear forbidden submatrices
• Linear bound on extremal functions of some forbidden patterns in 0-1 matrices
• Extremal functions of forbidden double permutation matrices
• On 0-1 matrices and small excluded submatrices
• An Extremal Problem on Sparse 0-1 Matrices
• Generalized Davenport-Schinzel sequences and their 0-1 matrix counterparts
• Extremal functions of excluded tensor products of permutation matrices
• Forbidden Hypermatrices Imply General Bounds on Induced Forbidden Subposet Problems
• Bounds on parameters of minimally nonlinear patterns
• Lower bounds on Davenport-Schinzel sequences via rectangular Zarankiewicz matrices
• 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
• Linear bounds on matrix extremal functions using visibility hypergraphs
• Better upper bounds on the Füredi-Hajnal limits of permutations
• On the Turán number of ordered forests

Cited In (7)

• An exact characterization of saturation for permutation matrices
• Saturation of Multidimensional 0-1 Matrices
• Saturation of Ordered Graphs
• Extremal bounds for pattern avoidance in multidimensional 0-1 matrices
• Sequence saturation
• Saturation problems about forbidden 0-1 submatrices
• On minimum saturated matrices

This page was built for publication: Almost all permutation matrices have bounded saturation functions

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