标题： 在超网格上测试禁止的顺序模式属性 显示英文标题

标题： Testing forbidden order-pattern properties on hypergrids

摘要： 我们研究函数$f:[n]^d\to\mathbb{R}$的$\pi$-无特性，其中$f$在存在没有$k$索引$x_1\prec\cdots\prec x_k\in [n]^d$使得$f(x_i)<f(x_j)$和$\pi(i) < \pi(j)$对所有$i,j \in [k]$成立时是$\pi$-无的，其中$\prec$是 over$[n]^d$的自然偏序。 给定$\epsilon\in(0,1)$，$\epsilon$-测试$\pi$-自由性要求区分$\pi$-自由函数和那些是$\epsilon$-远的函数——意味着至少需要修改$\epsilon n^d$个函数值才能使其成为$\pi$-自由。 虽然$k=2$与单调性测试一致，但对$k>2$知之甚少。 我们开始对高维网格上的模式自由进行系统研究。 对于$d=2$和所有大小为$k=3$的排列，我们设计了一个自适应的单边测试器，查询复杂度为$O(n^{4/5+o(1)})$。 我们还证明了$k=3$的一般下界：每个非自适应测试器需要$\Omega(n)$次查询，每个自适应测试器需要$\Omega(\sqrt{n})$次查询，从而得到了$\pi$-freeness 的第一个超对数下界。 对于单调模式$\pi=(1,2,3)$和$(3,2,1)$，我们提出了一个具有多项对数查询复杂度的非自适应测试器，给出了单调模式与非单调模式之间的指数分离（与一维情况不同）。 我们用于$\pi$-无性测试的关键成分是新的擦除弹性（$\delta$-ER）$\epsilon$-测试器，用于在$[n]^d$上的单调性，查询复杂度为$O(\log^{O(d)}n/(\epsilon(1-\delta)))$，其中$0<\delta<1$是擦除比例的上界。先前的 ER 测试器仅适用于$\delta=O(\epsilon/d)$。我们的非自适应单调性测试器通过 Pallavoor、Raskhodnikova 和 Waingarten 的匹配下界（Random Struct. Algorithms, 2022）几乎是最优的。 最后，我们证明，当前的技术无法在二维超网格上为长度为$4$的模式产生次线性查询的测试器。 显示英文摘要

摘要： We study testing $\pi$-freeness of functions $f:[n]^d\to\mathbb{R}$, where $f$ is $\pi$-free if there there are no $k$ indices $x_1\prec\cdots\prec x_k\in [n]^d$ such that $f(x_i)<f(x_j)$ and $\pi(i) < \pi(j)$ for all $i,j \in [k]$, where $\prec$ is the natural partial order over $[n]^d$. Given $\epsilon\in(0,1)$, $\epsilon$-testing $\pi$-freeness asks to distinguish $\pi$-free functions from those which are $\epsilon$-far -- meaning at least $\epsilon n^d$ function values must be modified to make it $\pi$-free. While $k=2$ coincides with monotonicity testing, far less is known for $k>2$. We initiate a systematic study of pattern freeness on higher-dimensional grids. For $d=2$ and all permutations of size $k=3$, we design an adaptive one-sided tester with query complexity $O(n^{4/5+o(1)})$. We also prove general lower bounds for $k=3$: every nonadaptive tester requires $\Omega(n)$ queries, and every adaptive tester requires $\Omega(\sqrt{n})$ queries, yielding the first super-logarithmic lower bounds for $\pi$-freeness. For the monotone patterns $\pi=(1,2,3)$ and $(3,2,1)$, we present a nonadaptive tester with polylogarithmic query complexity, giving an exponential separation between monotone and nonmonotone patterns (unlike the one-dimensional case). A key ingredient in our $\pi$-freeness testers is new erasure-resilient ($\delta$-ER) $\epsilon$-testers for monotonicity over $[n]^d$ with query complexity $O(\log^{O(d)}n/(\epsilon(1-\delta)))$, where $0<\delta<1$ is an upper bound on the fraction of erasures. Prior ER testers worked only for $\delta=O(\epsilon/d)$. Our nonadaptive monotonicity tester is nearly optimal via a matching lower bound due to Pallavoor, Raskhodnikova, and Waingarten (Random Struct. Algorithms, 2022). Finally, we show that current techniques cannot yield sublinear-query testers for patterns of length $4$ even on two-dimensional hypergrids.