The INI has a new website!

This is a legacy webpage. Please visit the new site to ensure you are seeing up to date information.

Skip to content



Is asymptotic extremal graph theory of dense graphs trivial?

Hatami, H (McGill)
Tuesday 14 June 2011, 14:00-15:00

Seminar Room 1, Newton Institute


Recent developments in asymptotic extremal combinatorics have provided powerful automatic and semi-automatic methods for proving theorems in the dense setting. For example I will show how relying completely on a computer, one can solve an old conjecture of Erdos and answer a question of Sidorenko and of Jagger, Stovicek and Thomason. These new discoveries raise the following fundamental question: ``is it possible to prove every true algebraic inequalities between graph densities using a finite amount of manipulation with densities of finitely many graphs?'' Although this question itself is not well-defined, various precise refinements of it are formulated independently by Razborov and Lovasz. I will present a joint theorem with Sergey Norin which answers many of these questions.


The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.

Back to top ∧