Miklós Simonovits
Instituto Alfréd Rényi de Matemática
Academia Húngara de Ciências
Sexta-feira, 28 de maio de 2004, 14:00
Sala de Conferências Antonio Gilioli, IME-USP
Resumo:
Extremal hypergraph problems seem to be much more difficult than ordinary extremal graph problems. Extremal multigraph problems seem to be somewhere in between. Recently, several new result were obtained in the area of extremal hypergraph problems, many of them, somewhat unexpectedly, providing the exact extremal hypergraphs, at least for $n$ sufficiently large.
Extremal graph results are strongly related to various colorings, while, one the other hand, certain types of colorings are connected to extremal problems. Often the exclusion of some subgraphs is weaker than a given chromatic condition, but the extremal graphs for the forbidden family and for the chromatic condition are the same. In these cases we often have some stability results as well, expressing that the chromatic conditions and extremal problems have the same extremal graphs because of some deeper reasons.
In my lecture I will give an introduction into the area, speak about this connection (to coloring) and also about some particular cases of hypergraph extremal problems. Some of the results will be joint with Füredi (on the extremal hypergraph problem of the excluded Fano plane), and the others with Füredi and Pikhurko.
(*) Visita ao IME--USP apoiada pela FAPESP (Proc.~FAPESP 2004/02440--9)