{
  "id": "1506.03874",
  "version": "v1",
  "published": "2015-06-11T23:50:07.000Z",
  "updated": "2015-06-11T23:50:07.000Z",
  "title": "Extremal Functions of Forbidden Multidimensional Matrices",
  "authors": [
    "Jesse T. Geneson",
    "Peter M. Tian"
  ],
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "Pattern avoidance is a central topic in graph theory and combinatorics. Pattern avoidance in matrices has applications in computer science and engineering, such as robot motion planning and VLSI circuit design. A $d$-dimensional zero-one matrix $A$ avoids another $d$-dimensional zero-one matrix $P$ if no submatrix of $A$ can be transformed to $P$ by changing some ones to zeros. A fundamental problem is to study the maximum number of nonzero entries in a $d$-dimensional $n \\times \\cdots \\times n$ matrix that avoids $P$. This maximum number, denoted by $f(n,P,d)$, is called the extremal function. We advance the extremal theory of matrices in two directions. The methods that we use come from combinatorics, probability, and analysis. Firstly, we obtain non-trivial lower and upper bounds on $f(n,P,d)$ when $n$ is large for every $d$-dimensional block permutation matrix $P$. We establish the tight bound $\\Theta(n^{d-1})$ on $f(n,P,d)$ for every $d$-dimensional tuple permutation matrix $P$. This tight bound has the lowest possible order that an extremal function of a nontrivial matrix can ever achieve. Secondly, we show that $f(n,P,d)$ is super-homogeneous for a class of matrices $P$. We use this super-homogeneity to show that the limit inferior of the sequence $\\{ {f(n,P,d) \\over n^{d-1}}\\}$ has a lower bound $2^{\\Omega(k^{1/ d})}$ for a family of $k \\times \\cdots \\times k$ permutation matrices $P$. We also improve the upper bound on the limit superior from $2^{O(k \\log k)}$ to $2^{O(k)}$ for all $k \\times \\cdots \\times k$ permutation matrices and show that the new upper bound also holds for tuple permutation matrices.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2015-06-11T23:50:07.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05D99"
    ],
    "keywords": [
      "extremal function",
      "forbidden multidimensional matrices",
      "upper bound",
      "dimensional zero-one matrix",
      "tight bound"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2015arXiv150603874G"
    }
  }
}