  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.
