{
  "id": "1805.05328",
  "version": "v1",
  "published": "2018-05-13T20:53:16.000Z",
  "updated": "2018-05-13T20:53:16.000Z",
  "title": "Forbidden formations in 0-1 matrices",
  "authors": [
    "Jesse Geneson"
  ],
  "comment": "11 pages",
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "Keszegh (2009) proved that the extremal function $ex(n, P)$ of any forbidden light $2$-dimensional 0-1 matrix $P$ is at most quasilinear in $n$, using a reduction to generalized Davenport-Schinzel sequences. We extend this result to multidimensional matrices by proving that any light $d$-dimensional 0-1 matrix $P$ has extremal function $ex(n, P,d) = O(n^{d-1}2^{\\alpha(n)^{t}})$ for some constant $t$ that depends on $P$. To prove this result, we introduce a new family of patterns called $(P, s)$-formations, which are a generalization of $(r, s)$-formations, and we prove upper bounds on their extremal functions. In many cases, including permutation matrices $P$ with at least two ones, we are able to show that our $(P, s)$-formation upper bounds are tight.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2018-05-13T20:53:16.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05D99"
    ],
    "keywords": [
      "forbidden formations",
      "extremal function",
      "formation upper bounds",
      "forbidden light",
      "permutation matrices"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 11,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}