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, Fisher , Krivelevich, Szegedy, Combinatoria 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.
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.
R
Fisher
Fischer
R
Combinatoria
Combinatorica