# Natural, untestable graph properties

In graph property testing, an algorithm queries a target graph for the presence or absence of edges and needs to determine whether the target either has a certain property or is $\epsilon$-far from having the property. (An algorithm can be asked to succeed with 1-sided or 2-sided error.) A graph is $\epsilon$-far from having a property if no $\epsilon \binom{n}{2}$ edges can be added/subtracted to make it have the property.

A property is said to be testable if it can be tested in the manner specified above in a sub-linear number of queries, or better yet, in a number of queries independent of $n$ (but not $\epsilon$). The notion of what properties are can also be formalized, but it should be clear.

There are many results characterizing what properties are testable, with many examples of natural testable properties. However, I am not aware of many natural properties that are known to not be testable (say in a constant number of queries) -- one that I am familiar with is testing for isomorphism to a given graph.

So, my question is: what natural graph properties are known not to be testable?

• (1) To clarify, are you looking for such properties in the adjacent matrix model? In the adjacency list model (which is different from the formulation you wrote), many problems require more than a constant number of queries. (2) You probably know this, but Goldreich, Goldwasser, and Ron (Proposition 10.2.3.2 of JACM 1998) prove that there is a (not necessarily natural) graph property in NP which requires Ω(n^2) queries by using the probabilistic method. – Tsuyoshi Ito Sep 25 '12 at 14:00
• Thanks - adjacency matrix model is fine. I know their result, but I'd like explicit natural properties, as opposed to the existence of some properties. – Lev Reyzin Sep 25 '12 at 14:25
• I'm not sure about it so I don't list it as an answer, but I think that the Shannon capacity of a graph $\Theta(G)$ is not testable. mathworld.wolfram.com/ShannonCapacity.html – Dimitris Oct 9 '12 at 11:36

In the adjacency matrix model, there is a lower bound of $\Omega(n)$ on the query complexity of testing whether an $n$ vertex graph consists of two isomorphic copies of some $n/2$-vertex graph (see Introduction to testing graph properties - Goldreich for a survey).
Also, there are many lower bounds that depend on $n$ for testers with one-sided error, e.g.: testing $\rho$-Clique,$\rho$-Cut, and $\rho$-Bisection (see Property testing and its connection to learning and approximation - Goldreich, Goldwasser, Ron)
Moreover, in the bounded degree graph model, testing 3-Colorability requires $\Omega(n)$ queries, whereas testing 2-Colorability (i.e., Bipartiteness) requires $\Omega(\sqrt n)$ (see Property testing in bounded degree graphs - Goldreich, Ron).