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