网站首页  |  实验室概况  |  研究团队  |  新闻中心  |  学术交流  |  学术报告  |  实验室年报  |  联系我们

 
 
  当前位置:首页 -> 学术报告
吴文俊数学重点实验室组合图论系列讲座之九十【Mikl′os Simonovits】
报告题目: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
中国科学院吴文俊数学重点实验室