{
  "id": "2105.02210",
  "version": "v1",
  "published": "2021-05-05T17:35:02.000Z",
  "updated": "2021-05-05T17:35:02.000Z",
  "title": "An exact characterization of saturation for permutation matrices",
  "authors": [
    "Benjamin Aram Berendsohn"
  ],
  "comment": "Supersedes arXiv:2012.14717, with text overlap",
  "categories": [
    "math.CO"
  ],
  "abstract": "A 0-1 matrix $M$ contains a 0-1 matrix pattern $P$ if we can obtain $P$ from $M$ by deleting rows and/or columns and turning arbitrary 1-entries into 0s. The saturation function $\\mathrm{sat}(P,n)$ for a 0-1 matrix pattern $P$ indicates the minimum number of 1s in an $n \\times n$ 0-1 matrix that does not contain $P$, but changing any 0-entry into a 1-entry creates an occurrence of $P$. Fulek and Keszegh recently showed that each pattern has a saturation function either in $O(1)$ or in $\\Theta(n)$. We fully classify the saturation functions of permutation matrices.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2021-05-05T17:35:02.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "permutation matrices",
      "exact characterization",
      "saturation function",
      "minimum number",
      "matrix pattern"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}