{
  "id": "2012.14150",
  "version": "v1",
  "published": "2020-12-28T08:54:02.000Z",
  "updated": "2020-12-28T08:54:02.000Z",
  "title": "Almost all permutation matrices have bounded saturation functions",
  "authors": [
    "Jesse Geneson"
  ],
  "categories": [
    "math.CO"
  ],
  "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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-12-28T08:54:02.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05D99"
    ],
    "keywords": [
      "bounded saturation functions",
      "permutation matrices",
      "saturation problem",
      "forbidden graphs",
      "popular area"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}