Logic Seminar
James Freitag
UIC
Nowhere dense classes of graphs
Abstract: Roughly speaking, a class of graphs is called nowhere dense if there is an upper bound on the size of a complete graph which occurs as an r-minor of an element of the class. This notion can also be characterized as there being a linear bound for the number of edges in terms of the number of vertices of any r-minor of an element of the class.
Nowhere density was introduced in the early 2000s, but was later noticed to be equivalent to the earlier notion of superflat, which is connected to model theory. In this talk, we will introduce the notions and explain the connections.
Tuesday February 17, 2026 at 2:00 PM in 427 SEO