Extremal functions of forbidden multidimensional matrices

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 Θ(nd−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 the limit inferior of the sequence {f(n,P,d)nd−1} has a lower bound 2Ω(k1∕2) for a family of k×⋯×k permutation matrices P. We also improve the upper bound on the limit superior from 2O(klogk) to 2O(k) for all k×⋯×k permutation matrices and show that the new upper bound also holds for tuple permutation matrices.