  Permutation pattern-avoidance is a central concept of both enumerative and
extremal combinatorics. In this paper we study the effect of permutation
pattern-avoidance on the complexity of optimization problems.
  In the context of the dynamic optimality conjecture (Sleator, Tarjan, STOC
1983), Chalermsook, Goswami, Kozma, Mehlhorn, and Saranurak (FOCS 2015)
conjectured that the amortized access cost of an optimal binary search tree
(BST) is $O(1)$ whenever the access sequence avoids some fixed pattern. They
showed a bound of $2^{\alpha{(n)}^{O(1)}}$, which was recently improved to
$2^{\alpha{(n)}(1+o(1))}$ by Chalermsook, Pettie, and Yingchareonthawornchai
(2023); here $n$ is the BST size and $\alpha(\cdot)$ the inverse-Ackermann
function. In this paper we resolve the conjecture, showing a tight $O(1)$
bound. This indicates a barrier to dynamic optimality: any candidate online BST
(e.g., splay trees or greedy trees) must match this optimum, but current
analysis techniques only give superconstant bounds.
  More broadly, we argue that the easiness of pattern-avoiding input is a
general phenomenon, not limited to BSTs or even to data structures. To
illustrate this, we show that when the input avoids an arbitrary, fixed, a
priori unknown pattern, one can efficiently compute a $k$-server solution of
$n$ requests from a unit interval, with total cost $n^{O(1/\log k)}$, in
contrast to the worst-case $\Theta(n/k)$ bound; and a traveling salesman tour
of $n$ points from a unit box, of length $O(\log{n})$, in contrast to the
worst-case $\Theta(\sqrt{n})$ bound; similar results hold for the euclidean
minimum spanning tree, Steiner tree, and nearest-neighbor graphs.
  We show both results to be tight. Our techniques build on the Marcus-Tardos
proof of the Stanley-Wilf conjecture, and on the recently emerging concept of
twin-width; we believe our techniques to be more generally applicable.
