Research Seminars @ Illinois

View Full Calendar

Tailored for undergraduate researchers, this calendar is a curated list of research seminars at the University of Illinois. Explore the diverse world of research and expand your knowledge through engaging sessions designed to inspire and enlighten.

To have your events added or removed from this calendar, please contact OUR at

Mathematics Colloquium: Sparsity from a game theoretic perspective

Event Type
Department of Mathematics
245 Altgeld Hall
Feb 22, 2024   4:00 pm  
Henry Kiersted (Arizona State University)
Jake Rasmussen
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.

link for robots only