The removal lemma for tournaments

摘要

Suppose one needs to change the direction of at least epsilon n(2) edges of an n-vertex tournament T, in order to make it H-free. A standard application of the regularity method shows that in this case T contains at least f(H)*(epsilon)n(h ) copies of H, where f(H)* is some tower-type function. It has long been observed that many graph/digraph problems become easier when assuming that the host graph is a tournament. It is thus natural to ask if the removal lemma becomes easier if we assume that the digraph G is a tournament.