Szemerédi Regularity Lemma and how to use it

Title:Szemerédi Regularity Lemma and how to use it

Speaker:匈牙利科学院院士Miklós Simonovits教授

时间:2018/06/07       16:00

地点:知新楼B819

邀请人:王光辉教授

Abstract:The Szemerédi Regularity Lemma has many forms, generalizations, extensions, however, I will restrict myself to the original Regularity Lemma. It says, in a more technical way that any graph can be approximated by a Generalized Random Graph.
In my lecture I shall introduce Random Graphs, Generalized Random Graphs, and formulate the Szemerédi Regularity Lemma. I shall explain its usage on two examples, the Ramsey-Turán theorem of $K_4$, and the Ruzsa-Szemerédi theorem. To this end I shall also define the Cluster Graphs, and speak about the $K_3$-removal Lemma and about the general Graph Removal Lemma.

Miklós Simonovits院士简介:匈牙利Alfréd Rényi 数学研究所教授,匈牙利科学院院士,主要研究兴趣为极值图论和随机图,是享誉国际的图论与组合数学专家。Simonovits 院士是上世纪世界著名数学家1983年沃尔夫奖获得者Erdős的重要合作伙伴,与其合作发表论文21篇;同时是当今世界著名数学家1999年沃尔夫奖获得者Lovász(曾担任国际数学联盟主席)和2012年阿贝尔奖获得者Szemerédi的重要合作伙伴,合作完成了诸多重要研究工作。Simonovits院士累计在国际顶级期刊发表论文100余篇,被引4800余次,是当今匈牙利组合学派的杰出代表,于2014年荣获匈牙利最高科学技术奖Széchenyi奖。