Let H be a fixed graph with h vertices, let G be a graph on n vertices, and suppose that at least ∈n2 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)nh 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.
|Original language||English (US)|
|Number of pages||12|
|Journal||Random Structures and Algorithms|
|State||Published - 2002|
All Science Journal Classification (ASJC) codes
- Computer Graphics and Computer-Aided Design
- Applied Mathematics