Almost all permutation matrices have bounded saturation functions

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 $n\times n$ 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 $k\times k$ 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 $k\times k$ 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.