Abstract
LetHbe a fixed graph withhvertices, letGbe a graph onnvertices, and suppose that at least ϵn2edges have to be deleted from it to make itH‐free. It is known that in this caseGcontains at leastf(ϵ,H)nhcopies ofH.We show that the largest possible functionf(ϵ,H) is polynomial in ϵ if and only ifHis bipartite. This implies that there is a one‐sided error property tester for checkingH‐freeness, whose query complexity is polynomial in 1/ϵ,if and only if His bipartite. © 2002 Wiley Periodicals, Inc. Random Struct. Alg., 21: 359–370, 2002

This publication has 20 references indexed in Scilit: