Gábor Kun: A polynomial removal lemma for posets

Alon and Shapira proved that every monotone class of graphs is strongly testable. In other words, for every (possibly infinite) set F of forbidden subgraphs and every eps>0 there exists C(eps) such that for every graph G if the subgraph induced by C(eps) vertices chosen uniformly at random is with probability at least half F-free, then we can obtain an F-free graph G' on V(G) by the removal of at most eps|V(G)|^2 edges. The dependence of C(eps) on eps might be astronomical. We show that for posets C(eps) can be a polynomial of eps. Hence classes of posets defined by forbidden subposets are easily testable (according to the definition of Alon and Fox). Our results apply to comparability graphs, too. Joint work with Panna Fekete.