Property Testing in Hypergraphs and the Removal Lemma (Extended Abstract)
Mathias Schacht · 2007
Property testers are ecient, randomized algorithms which recognize if an input graph (or other combinatorial structure) satisfies a given property or if it is “far” from exhibiting it. Generalizing several earlier results, Alon and Shapira showed that hereditary graph properties are testable (with one-sided error). In this paper we prove the analogous result for hypergraphs. This result is an immediate consequence of a (hyper)graph theoretic statement, which is an extension of the so-called removal lemma. The proof of this generalization relies on the regularity method for hypergraphs.