Almost all permutation matrices have bounded saturation functions (Q831345): Difference between revisions

Summary: Saturation problems for forbidden graphs have been a popular area of research for many decades, and recently \textit{R. A. Brualdi} and \textit{L. Cao} [``Pattern-avoiding (0, 1)-matrices'', Preprint, \url{arXiv:2005.00379}] initiated the study of a saturation problem for 0-1 matrices. We say that a 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 \(\text{sat}(n, P)\) to be the minimum possible number of ones in an \(n \times n\) 0-1 matrix that is saturating for \(P\). \textit{R. Fulek} and \textit{B. Keszegh} [``Saturation problems about forbidden 0-1 submatrices'', Preprint, \url{arXiv:2010.08256}] proved that for every 0-1 matrix \(P\), either \(\operatorname{sat}(n, P) = O(1)\) or \(\operatorname{sat}(n, P) = \Theta(n)\). They found two 0-1 matrices \(P\) for which \(\text{sat}(n, P) = O(1)\), as well as infinite families of 0-1 matrices \(P\) for which \(\operatorname{sat}(n, P) = \Theta(n)\). Their results imply that \(\text{sat}(n, P) = \Theta(n)\) for almost all \(k \times k\) 0-1 matrices \(P\). Fulek and Keszegh [loc. cit.] conjectured that there are many more 0-1 matrices \(P\) such that \(\operatorname{sat}(n, P) = O(1)\) besides the ones they found, and they asked for a characterization of all permutation matrices \(P\) such that \(\operatorname{sat}(n, P) = O(1)\). We affirm their conjecture by proving that almost all \(k \times k\) permutation matrices \(P\) have \(\operatorname{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.