Testing forbidden order-pattern properties on hypergrids

Given a permutation \(\pi:[k]\to[k]\), a function \(f:[n]^{d}\to\mathbb{R}\) is said to be \(\pi\)-free if there are no \(k\) indices \(x_{1}\prec\cdots\prec x_{k}\in[n]^{d}\) such that \(f(x_{i})\lt f(x_{j})\) and \(\pi(i)\lt \pi(j)\) for all \(i,j\in[k]\), where \(\prec\) is the natural partial order over \([n]^{d}\). For a fixed \(\pi\) and \(\epsilon\in(0,1)\), the problem of \(\epsilon\)-testing \(\pi\)-freeness is to distinguish the case that \(f\) is \(\pi\)-free from the case that at least \(\epsilon n^{d}\) values of \(f\) need to be modified in order to make it \(\pi\)-free. When \(k=2\), the problem is identical to monotonicity testing, which is extensively studied in property testing. The case of \(k>2\) has also received significant attention for functions \(f:[n]\to\mathbb{R}\).