  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.
