Logical methods for property testing in the bounded degree model

Property testers are randomised sublinear time algorithms which infer global structure from a local view of an input. In the context of bounded degree graphs, testability of a property is tightly linked to the question of whether an approximate distribution of r-neighbourhood types of a graph is sufficient to capture whether the graph has the property or is “far” from having the property. Our understanding of when this is the case is limited. The central open question in the field of property testing is to characterise testable properties of bounded degree graphs. Towards a characterisation of testable properties in the bounded degree model, we study property testing of properties definable in first-order logic (FO) in the bounded degree model. By Gaifman’s locality theorem it is known that FO can only express local properties. On the other hand, testers can explore only local neighbourhoods and hence locality is necessary for testability. We prove however, that the notion of locality imposed by being definable in FO is not sufficient for property testing. More precisely, we show that there is a non-testable property defined by an FO-sentence whose quantifier prefix contains only one quantifier alternation of the form “∀∃”. We complement this by proving that every FO-sentence not containing a quantifier alternation of the form “∀∃” can be tested with a constant number of queries. We further identify some classes of FO-sentences which yield testable properties and contain quantifier alternations of the form “∀∃”. These sentences express that the distribution of r-neighbourhood types is of a particular, simple form. We explore the connection between the notion of locality imposed by FO and the notion of locality necessary for testability further. We establish links between FO definability and a generalised notion of subgraph freeness. This notion was introduced in the context of character- ising one-sided error proximity oblivious testers, a particularly simple type of testers. Using a variation of our non-testable FO definable property we show that generalised subgraph freeness does equally not capture the locality needed for testability, which answers an open question regarding the characterisation of testable properties in the bounded degree model. Going beyond FO definability, we explore hardness of property testing problems in connec- tion with classical complexity theory. We obtain a deterministic construction of hard instances for property testing Hamiltonicity, which is a known non-testable property. This construc- tion is interesting from the perspective of exploring links between structural properties and non-testability. We further utilise the lower bound technique developed in the context of our non-testable FO definable property to prove non-testability of having treewidth logarithmic in the number of vertices.