{
  "id": "math/0507164",
  "version": "v1",
  "published": "2005-07-08T17:33:50.000Z",
  "updated": "2005-07-08T17:33:50.000Z",
  "title": "Extensions of the linear bound in the Furedi-Hajnal conjecture",
  "authors": [
    "Martin Klazar",
    "Adam Marcus"
  ],
  "comment": "11 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "We present two extensions of the linear bound, due to Marcus and Tardos, on the number of 1's in an n by n 0-1 matrix avoiding a fixed permutation matrix. We first extend the linear bound to hypergraphs with ordered vertex sets and, using previous results of Klazar, we prove an exponential bound on the number of hypergraphs on n vertices which avoid a fixed permutation. This, in turn, solves various conjectures of Klazar as well as a conjecture of Branden and Mansour.We then extend the original Furedi-Hajnal problem from ordinary matrices to d-dimensional matrices and show that the number of 1's in a d-dimensional 0-1 matrix with side length n which avoids a d-dimensional permutation matrix is O(n^{d-1}).",
  "revisions": [
    {
      "version": "v1",
      "updated": "2005-07-08T17:33:50.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05D05",
      "05A16"
    ],
    "keywords": [
      "linear bound",
      "furedi-hajnal conjecture",
      "extensions",
      "d-dimensional permutation matrix",
      "original furedi-hajnal problem"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 11,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2005math......7164K"
    }
  }
}