Combinatorics Seminar

When: Sunday, May 17, 10am Where: Schreiber 309 Speaker: Lior Gishboliner, Tel Aviv University Title: A removal lemma for tournaments

Abstract:

Suppose one needs to change the direction of at least \eps*n^2 edges of an n-vertex tournament G, in order to make it H-free. A standard application of the regularity method shows that in this case G contains f(\eps,H)n^h copies of H, where h is the number of vertices of H and f is some horrible tower-type function. Motivated by several related studies, we consider the problem of characterizing the tournaments H for which f is polynomial in \eps.

Joint work with A. Shapira and R. Yuster