Every minor-closed property of sparse graphs is testable
Itaï Benjamini, Oded Schramm, A. Shapira · Advances in Mathematics · 2008
Suppose G is a graph of bounded degree d , and one needs to remove ϵn of its edges in order to make it planar. We show that in this case the statistics of local neighborhoods around vertices of G is far from the statistics of local neighborhoods around vertices of any planar graph G ′ . In fact, a similar result is proved for any minor-closed property of bounded degree graphs. The main motivation of the above result comes from theoretical computer-science. Using our main result we infer that for any minor-closed property P , there is a constant time algorithm for detecting if a graph is “far” from satisfying P . This, in particular, answers an open problem of Goldreich and Ron [STOC 1997] [20] , who asked if such an algorithm exists when P is the graph property of being planar. The proof combines results from the theory of graph minors with results on convergent sequences of sparse graphs, which rely on martingale arguments.