  The theory of forbidden 0-1 matrices generalizes Turan-style (bipartite)
subgraph avoidance, Davenport-Schinzel theory, and Zarankiewicz-type problems,
and has been influential in many areas, such as discrete and computational
geometry, the analysis of self-adjusting data structures, and the development
of the graph parameter twin width.
  The foremost open problems in this area is to resolve the Pach-Tardos
conjecture from 2005, which states that if a forbidden pattern
$P\in\{0,1\}^{k\times l}$ is the bipartite incidence matrix of an acyclic graph
(forest), then $\mathrm{Ex}(P,n) = O(n\log^{C_P} n)$, where $C_P$ is a constant
depending only on $P$. This conjecture has been confirmed on many small
patterns, specifically all $P$ with weight at most 5, and all but two with
weight 6.
  The main result of this paper is a clean refutation of the Pach-Tardos
conjecture. Specifically, we prove that $\mathrm{Ex}(S_0,n),\mathrm{Ex}(S_1,n)
\geq n2^{\Omega(\sqrt{\log n})}$, where $S_0,S_1$ are the outstanding weight-6
patterns. We also prove sharp bounds on the entire class of alternating
patterns $(P_t)$, specifically that for every $t\geq 2$,
$\mathrm{Ex}(P_t,n)=\Theta(n(\log n/\log\log n)^t)$. This is the first proof of
an asymptotically sharp bound that is $\omega(n\log n)$.
