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 /spl epsi/n/sup 2/ edges have to be deleted from it to make it H-free. It is known that in this case G contains at least f (/spl epsi/, H)n/sup h/ copies of H. We show that the largest possible function f (/spl epsi/, H) is polynomial in /spl epsi/ 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//spl epsi/, if and only if H is bipartite.

Authors

• Noga Alon

Keywords

• Testing
• Polynomials
• Computer science
• Mathematics
• Information geometry
• Chromium
• Sufficiently Large
• Vertices
• Homomorphism
• Graph Properties
• Graph Size
• Input Graph
• Adjacent Vertices