2017
Mar
23

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

2:30pm to 3:30pm

## Location:

Manchester Building (Hall 2), Hebrew University Jerusalem

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