cs.LO cs.CC cs.DM cs.DS math.CO
On Testability of First Order Properties in Bounded Degree Graphs. 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.