报告题目：Extremal theory of vertex- and edge-ordered graphs
报告人： Gabor Tardos 教授（Renyi Institute of Hungarian Academy of Science）
报告时间：2022年4月8日、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.
邀请人：朱绪鼎