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

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