{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T16:43:44Z","timestamp":1753893824011,"version":"3.41.2"},"reference-count":0,"publisher":"The Electronic Journal of Combinatorics","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Electron. J. Combin."],"abstract":"<jats:p>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 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 $\\mathrm{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 $\\mathrm{sat}(n, P) = O(1)$ or $\\mathrm{sat}(n, P) = \\Theta(n)$. They found two 0-1 matrices $P$ for which $\\mathrm{sat}(n, P) = O(1)$, as well as infinite families of 0-1 matrices $P$ for which $\\mathrm{sat}(n, P) = \\Theta(n)$. Their results imply that $\\mathrm{sat}(n, P) = \\Theta(n)$ for almost all $k \\times k$ 0-1 matrices $P$.\r\nFulek and Keszegh conjectured that there are many more 0-1 matrices $P$ such that $\\mathrm{sat}(n, P) = O(1)$ besides the ones they found, and they asked for a characterization of all permutation matrices $P$ such that $\\mathrm{sat}(n, P) = O(1)$. We affirm their conjecture by proving that almost all $k \\times k$ permutation matrices $P$ have $\\mathrm{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.<\/jats:p>","DOI":"10.37236\/10124","type":"journal-article","created":{"date-parts":[[2021,5,6]],"date-time":"2021-05-06T10:25:22Z","timestamp":1620296722000},"source":"Crossref","is-referenced-by-count":2,"title":["Almost all Permutation Matrices have Bounded Saturation Functions"],"prefix":"10.37236","volume":"28","author":[{"given":"Jesse","family":"Geneson","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"23455","published-online":{"date-parts":[[2021,5,7]]},"container-title":["The Electronic Journal of Combinatorics"],"original-title":[],"link":[{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v28i2p16\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v28i2p16\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,6]],"date-time":"2021-05-06T10:25:22Z","timestamp":1620296722000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/view\/v28i2p16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,5,7]]},"references-count":0,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2021,4,9]]}},"URL":"https:\/\/doi.org\/10.37236\/10124","relation":{},"ISSN":["1077-8926"],"issn-type":[{"type":"electronic","value":"1077-8926"}],"subject":[],"published":{"date-parts":[[2021,5,7]]},"article-number":"P2.16"}}