  The extremal theory of forbidden 0-1 matrices studies the asymptotic growth
of the function $\mathrm{Ex}(P,n)$, which is the maximum weight of a matrix
$A\in\{0,1\}^{n\times n}$ whose submatrices avoid a fixed pattern
$P\in\{0,1\}^{k\times l}$. This theory has been wildly successful at resolving
problems in combinatorics, discrete and computational geometry, structural
graph theory, and the analysis of data structures, particularly corollaries of
the dynamic optimality conjecture.
  All these applications use acyclic patterns, meaning that when $P$ is
regarded as the adjacency matrix of a bipartite graph, the graph is acyclic.
The biggest open problem in this area is to bound $\mathrm{Ex}(P,n)$ for
acyclic $P$. Prior results have only ruled out the strict $O(n\log n)$ bound
conjectured by Furedi and Hajnal. It is consistent with prior results that
$\forall P. \mathrm{Ex}(P,n)\leq n\log^{1+o(1)} n$, and also consistent that
$\forall \epsilon>0.\exists P. \mathrm{Ex}(P,n) \geq n^{2-\epsilon}$.
  In this paper we establish a stronger lower bound on the extremal functions
of acyclic $P$. Specifically, we give a new construction of relatively dense
0-1 matrices with $\Theta(n(\log n/\log\log n)^t)$ 1s that avoid an acyclic
$X_t$. Pach and Tardos have conjectured that this type of result is the best
possible, i.e., no acyclic $P$ exists for which $\mathrm{Ex}(P,n)\geq n(\log
n)^{\omega(1)}$.
