报告题目：Stability method in Extremal Graph Theory and related areas
报告人：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 an n-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 applications of the stability method in extremal graph theory, and also some results of Paul Erd˝os and myself in the theory of Dual Anti-Ramsey problems. The stability method was first applied by Simonovits and Erd˝os, in the 1970’s. It became one of the most powerful methods in Extremal Graph Theory, and related areas. One example is Theorem 1 (Erd˝os-Simonovits). For any L, the extremal graphs Sn are very similar to Tn,p, if p := min L∈L χ(L) − 1, in the following sense: one can delete and add o(n 2 ) edges of any extremal graph Sn to get a Tur′an graph Tn,p, as n → ∞. The corresponding stability theorem asserts that not only the almost extremal graphs Gn also have almost the same structure as Tn,p. Theorem 2 (Erd˝os-Simonovits). If Gn does not contain subgraphs L ∈ L and e(Gn) > ex(n,L) − o(n 2 ), then one can delete and add o(n 2 ) edges of Gn to get a Tn,p. One application of the stabiltiy method is the proof of the famous Erd˝os-S′os conjecture on trees, another one was the proof of the conjecture of S′os, on Fano-free hypergraphs, by F¨uredi and Simonovits, and Keevash and Sudakov. This method was used to prove further exact hypergraph extremal results, and sharp versions of some results of Erd˝os, Frankl, and R¨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 author settled several open questions. Here we mention just one. Theorem 3 (Erd˝os-Simonovits). There exists a threshold n0 such that if n > n0, and a graph Gn has 1 4 n 2 + 1 edges and we edge-colour its edges so that every C5 is 5–coloured, then we have to use at least n 2 + 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
