It feels a bit awkward to recommend a paper that resolves a problem posed by myself (in a paper with Igor Shinkar), but this may compensate on my timidness for publicizing my favorite open problems, let alone giving talks on my works...
Anyhow, the problem addressed is the complexity of testing properties that are defined in terms of a (fixed) linear inequality regarding the densities of various subgraphs. For example, consider the set of graphs in which the sum of the frequencies of induced four-cycles and four-cliques is at most one third. The current paper shows that the query complexity of testing such properties, even with respect to four-vertex patterns, must grow with the size of the input graph (i.e., it is not testable within complexity that only depends on the proximity parameter). The proof is based on the observation that while constant-query testers may not distinguish a sufficiently large graph from its (equal-factor) blow-up, some of these properties are not closed under such blow-up.
I wish to protest, yet again, against defining testability as testability within size-oblivious query complexity. I also disagree with the general assertion by which such tester operate by inspecting a small randomly selected portion of the input; this is true, up to some slackness, in the case of testing graph properties in the dense graph model (see here), but is not true in general.
Property testers are fast randomized algorithms whose task is to distinguish between inputs satisfying some predetermined property and those that are far from satisfying it. Since these algorithms operate by inspecting a small randomly selected portion of the input, the most natural property one would like to be able to test is whether the input does not contain certain forbidden small substructures. In the setting of graphs, such a result was obtained by Alon et al., who proved that for any finite family of graphs F, the property of being induced F-free (i.e. not containing an induced copy of any graph in F) is testable. It is natural to ask if one can go one step further and prove that more elaborate properties involving induced subgraphs are also testable. One such generalization of the result of Alon et al. was formulated by Goldreich and Shinkar who conjectured that for any finite family of graphs F, and any linear inequality involving the densities of the graphs of F in the input graph, the property of satisfying this inequality can be tested in a certain restricted model of graph property testing. Our main result in this paper disproves this conjecture in the following strong form: some properties of this type are not testable even in the classical (i.e. unrestricted) model of graph property testing. The proof deviates significantly from prior non-testability results in this area. The main idea is to use a linear inequality relating induced subgraph densities in order to encode the property of being a pseudo-random graph.
See proceedings of 11th ITCS.