Mathematics Colloquium: Sparsity from a game theoretic perspective

Event Type

Seminar/Symposium

Sponsor

Department of Mathematics

Location

245 Altgeld Hall

Date

Feb 22, 2024   4:00 pm  

Speaker

Henry Kiersted (Arizona State University)

Contact

Jake Rasmussen

E-Mail

rasmusj@illinois.edu

Views

80

Originating Calendar

Mathematics Colloquium & Named Lectures

Abstract: 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. Nesetril 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.