id: 05689469
dt: j
an: 05689469
au: Benjamini, Itai; Schramm, Oded; Shapira, Asaf
ti: Every minor-closed property of sparse graphs is testable.
so: Adv. Math. 223, No. 6, 2200-2218 (2010).
py: 2010
pu: Elsevier Science (Academic Press), San Diego, CA
la: EN
cc: 
ut: minor closed; property testing; sparse graphs; hyper finite
ci: Zbl 0990.68103
li: doi:10.1016/j.aim.2009.10.018
ab: Summary: 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{^{\prime}}$. 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 $\cal
    P$, there is a constant time algorithm for detecting if a graph is
    “far” from satisfying $\cal P$. This, in particular, answers an
    open problem of {\it O. Goldreich} and {\it D. Ron} [Algorithmica 32,
    No. 2, 302-343 (2002; Zbl 0990.68103)], who asked if such an algorithm
    exists when $\cal P$ is the graph property of being planar. The proof
    combines results from the theory of graph minors with results on
    convergent sequenc-es of sparse graphs, which rely on martingale
    arguments.
rv: