报告题目：Sparsity from a game theoretic perspective

报告人：H.A. Kierstead，亚利桑那州立大学

报告时间：2023年10月27日（周五）15:00-16:00

报告地点：21-427

报告摘要：Nešetřil and Ossona de Mendez introduced the notion of graph classes with bounded expansion and the more general notion of nowhere-dense graph classes. These concepts generalize those of graph classes with bounded tree-width, minor-closed classes, bounded degree classes, etc. This classification is informative as many inferesting properties of simple sparse classes are shared with more general classes, while results on the general classes can often be sharpened for simpler classes. Moreover, the Nešetril-Ossona de Mendez formulation is remarkably robust; there are many apparently disparate notions that turn out to be equivalent.

In applications it is often useful to use characterizations due to Zhu of bounded-expansion or nowhere-dense classes in terms of the generalized coloring numbers scol,(G) of a graph G. These numbers had been introduced earlier by Yang and me to extend the classes of graphs known to have bounded generalized game coloring numbers. Zhu's result implies that these are exactly the classes with bounded expansion. For each distance r, the strong r-coloring number scol,(G) is determined by an optimal ordering of the vertices of G. We study the question of whether it is possible to find a single uniform ordering that is. good for all distances r. We show that the answer to this question is essentially yes. Our results give new characterizations of bounded-expansion and nowhere-dense graph classes.

Much of this talk will be on joint work with Jan van den Heuvel, Department of Mathematics, London School of Economics and Political Science.

报告人简介：H.A. Kierstead，亚利桑那州立大学数学与统计科学学院教授。

邀请人：朱绪鼎