Testing subgraphs in directed graphs
Noga Alon, A. Shapira · 2003
Let H be a fixed directed graph on h vertices, let G be a directed graph on n vertices and suppose that at least ε n2 edges have to be deleted from it to make it H-free. We show that in this case G contains at least f(ε,H) nh copies of H. This is proved by establishing a directed version of Szemeredi's regularity lemma, and implies that for every H there is a one-sided error property tester whose query complexity is bounded by a function of ε only for testing the property PH of being H-free.