论文标题
关于有限度图中一阶性能的测试性
On Testability of First-Order Properties in Bounded-Degree Graphs
论文作者
论文摘要
我们研究了在界度图和关系结构模型中在一阶逻辑（FO）中可定义的属性的性质测试。我们表明，由具有量词前缀$ \ contists^*\ forall^*$定义的任何FO属性是可测试的（即，可测试具有恒定查询复杂性的测试），而虽然存在具有量子属性的fo属性，该属性可通过量词前prepix prepix $ \ forall^forall^*\ forall^*\ event^*$进行测试。在密集的图模型中，尽管这两个模型的性质截然不同，但长期以来的图像是悠久的（Alon，Fischer，Krivelevich，Szegedy，Combinatorica 2000）。特别是，我们通过基于图形的锯齿形产物来定义一类有界水平扩展器的一阶公式获得下限。我们希望这将具有独立的利益。然后，我们证明了一些一阶属性的可检验性，这些属性涉及社区的同构类型，包括$ 1 $ -neighbourhood-oferessions的可检验性，以及在该学位的温和假设下的$ R $ -R $ -NEIGHBORHOOD-FRESISES。
We study property testing of properties that are definable in first-order logic (FO) in the bounded-degree graph and relational structure models. We show that any FO property that is defined by a formula with quantifier prefix $\exists^*\forall^*$ is testable (i.e., testable with constant query complexity), while there exists an FO property that is expressible by a formula with quantifier prefix $\forall^*\exists^*$ that is not testable. In the dense graph model, a similar picture is long known (Alon, Fischer, Krivelevich, Szegedy, Combinatorica 2000), despite the very different nature of the two models. In particular, we obtain our lower bound by a first-order formula that defines a class of bounded-degree expanders, based on zig-zag products of graphs. We expect this to be of independent interest. We then prove testability of some first-order properties that speak about isomorphism types of neighbourhoods, including testability of $1$-neighbourhood-freeness, and $r$-neighbourhood-freeness under a mild assumption on the degrees.
