Abstrakt
Permutation pattern-avoidance is a central concept of both enumerative and extremal combinatorics. 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 search cost of an optimal binary search tree (BST) is constant whenever the search sequence is pattern-avoiding
More broadly, we argue that the easiness of pattern-avoiding input is a general phenomenon, not limited to BSTs or even to data structures.