报告人：Mikl′os Simonovits     Alfr′ed R′enyi Mathematical Institute, Budapest

报告时间：11月18日  2：00-3：00

报告地点：1218

摘要：Given a family L of excluded graphs, ex(n,L) is the maximum number of edges of ann-vertex graph not containing any L ∈ L. The related area is Extremal Graph Theory,the optimal graphs are also called extremal. I shall survey the wide area of applicationsof the stability method in extremal graph theory, and also some results of Paul Erd˝os andmyself in the theory of Dual Anti-Ramsey problems. The stability method was first appliedby Simonovits and Erd˝os, in the 1970’s. It became one of the most powerful methods inExtremal Graph Theory, and related areas. One example isTheorem 1 (Erd˝os-Simonovits). For any L, the extremal graphs Sn are very similar toTn,p, ifp := minL∈Lχ(L) − 1,in the following sense: one can delete and add o(n2) edges of any extremal graph Sn to geta Tur′an graph Tn,p, as n → ∞.The corresponding stability theorem asserts that not only the almost extremal graphsGn also have almost the same structure as Tn,p.Theorem 2 (Erd˝os-Simonovits). If Gn does not contain subgraphs L ∈ L ande(Gn) > ex(n,L) − o(n2),then one can delete and add o(n2) edges of Gn to get a Tn,p.One application of the stabiltiy method is the proof of the famous Erd˝os-S′os conjectureon trees, another one was the proof of the conjecture of S′os, on Fano-free hypergraphs, byF¨uredi and Simonovits, and Keevash and Sudakov. This method was used to prove furtherexact hypergraph extremal results, and sharp versions of some results of Erd˝os, Frankl, andR¨odl, on the typical structure of L-free graphs.The last part of my lecture will be on dual Anti-Ramsey theorems. Erd˝os and the authorsettled several open questions. Here we mention just one.Theorem 3 (Erd˝os-Simonovits). There exists a threshold n0 such that if n > n0, and agraph Gn has 14n2 + 1 edges and we edge-colour its edges so that every C5 is 5�coloured,then we have to use at least n2 + 3 colours.Here, beside Erd˝os, I should also have mentioned several coauthors or independent authors,like Babai, Balogh, Bollob′as, F¨uredi, Kohayakawa, Keevash and Sudakov, Pikhurko,Skokan, Spencer, and many others.1