Testing Subgraphs in Large Graphs

Let H be a fixed graph with h vertices, let G be a graph on n vertices, and suppose that at least ∈n² edges have to be deleted from it to make it H-free. It is known that in this case G contains at least f(∈, H)n^h copies of H. We show that the largest possible function f(∈, H) is polynomial in e if and only if H is bipartite. This implies that there is a one-sided error property tester for checking H-freeness, whose query complexity is polynomial in 1/∈, if and only if H is bipartite.