Colloquium: Asaf Shapira (Tel Aviv) - "Removal Lemmas with Polynomial Bounds"

A common theme in many extremal problems in graph theory is the relation between local and global properties of graphs. We will consider the following variant of this theme: suppose a graph G is far (in some well defined sense) from satisfying property P. Must G contain a small proof of this fact? We will show that for many natural graph properties the answer is Yes. In particular, we will show that the answer is Yes whenever P is a semi-algebraic graph property, thus conforming a conjecture of Alon. Joint work with L. Gishboliner


Thu, 23/03/2017 - 14:30 to 15:30


Manchester Building (Hall 2), Hebrew University Jerusalem