  A sequence $f\colon\{1,\dots,n\}\to\mathbb{R}$ contains a permutation $\pi$
of length $k$ if there exist $i_1<\dots<i_k$ such that, for all $x,y$,
$f(i_x)<f(i_y)$ if and only if $\pi(x)<\pi(y)$; otherwise, $f$ is said to be
$\pi$-free. In this work, we consider the problem of testing for $\pi$-freeness
with one-sided error, continuing the investigation of [Newman et al., SODA'17].
  We demonstrate a surprising behavior for non-adaptive tests with one-sided
error: While a trivial sampling-based approach yields an $\varepsilon$-test for
$\pi$-freeness making $\Theta(\varepsilon^{-1/k} n^{1-1/k})$ queries, our lower
bounds imply that this is almost optimal for most permutations! Specifically,
for most permutations $\pi$ of length $k$, any non-adaptive one-sided
$\varepsilon$-test requires
$\varepsilon^{-1/(k-\Theta(1))}n^{1-1/(k-\Theta(1))}$ queries; furthermore, the
permutations that are hardest to test require
$\Theta(\varepsilon^{-1/(k-1)}n^{1-1/(k-1)})$ queries, which is tight in $n$
and $\varepsilon$.
  Additionally, we show two hierarchical behaviors here. First, for any $k$ and
$l\leq k-1$, there exists some $\pi$ of length $k$ that requires
$\tilde{\Theta}_{\varepsilon}(n^{1-1/l})$ non-adaptive queries. Second, we show
an adaptivity hierarchy for $\pi=(1,3,2)$ by proving upper and lower bounds for
(one- and two-sided) testing of $\pi$-freeness with $r$ rounds of adaptivity.
The results answer open questions of Newman et al. and [Canonne and Gur,
CCC'17].
