Sparsity from a game theoretic perspective
H.A. Kierstead, School of Mathematical & Statistical Sciences, Arizona State University
In many applications of graph theory to computer science, operations research, logic, and game theory, people are interested in various notions of sparse graphs—graphs with few edges. Common examples include graph classes whose members have bounded maximum degree, bounded genus, or bounded tree-width. Nešetřil and Ossona de Mendez introduced a formal classification of sparsity for infinite classes of finite graphs with the notion of classes with bounded expansion and the more general notion of nowhere-dense classes. This classification, which includes the motivating examples mentioned above, is informative as there are many interesting properties shared by all such sparse classes. Furthermore, interesting properties of specific classes can often be generalized to all classes, while results on general classes can often be sharpened for specific classes. Additionally, this formulation is remarkably robust; there are many apparently disparate notions that are in fact equivalent. In this talk I will discuss how this theory has benefitted from the study of graph coloring games and graph ordering games.
