Renyi Institute of Hungarian Academy of Science Gabor Tardos 教授


报告题目:Extremal theory of vertex- and edge-ordered graphs

报告人: Gabor Tardos 教授(Renyi Institute of Hungarian Academy of Science

报告时间:202248日、4月15日 下午14:30-15:30

报告地点:腾讯会议ID: 949-970-364

摘要:Turán type extremal theory of graphs has a long history and can boast with a wide array of application in many parts of mathematics and theoretical computer science. It has been extended in many directions including hypergraphs, geometric and topological graphs among others. In these series of two introductory survey talks I will speak about recent extensions to vertex- and edge-ordered graphs.

       The classical theory asks the following question. Given a forbidden pattern, a simple graph H, what is the most edges a simple graph G on n vertices can have without containing H as a subgraph? In the extensions the forbidden pattern is endowed with some additional structure. For example, in the vertex-ordered case, the forbidden pattern H comes with a specified linear order on its vertices and we are looking for a simple graph G also with a linear order on its vertices that does not contain H with the given vertex-order (but may contain isomorphic copies of H with a different vertex-order).

      The talks will sample classical results from the Turán type extremal graph theory that carry over to vertex- or edge-ordered graphs and show some other classical results that do not carry over.  Some geometric applications of the new theory will be shown and the talks will include many open problems. 




浙江师范大学离散数学研究中心版权所有 © 2018-2028
地址:浙江省金华市迎宾大道688号21幢 邮政编码:321004
联系电话:0579-82282629   电子邮箱    管理登陆