Reproving combinatorial properties of nowhere-dense graphs using model theory

Speaker(s)

Wojciech Przybyszewski

Affiliation

MIM UW

Date

March 22, 2023, 2:15 p.m.

Room

room 5050

Seminar

Seminar Automata Theory

---

A pinnacle of sparsity theory, initiated by Ossona de Mendez and Nešetřil, is the result of Grohe, Kreutzer, and Siebertz which identifies subgraf-closed classes of graphs with FPT model checking as exactly nowhere dense classes. One of the key steps in the proof is characterizing nowhere dense classes of graphs in terms of a game called the Splitter game. There is an ongoing effort aimed at generalizing sparsity theory to classes of graphs that are not necessarily sparse. One of the most recent steps toward this goal is an analogous characterization of monadically stable classes of graphs (which contain FO-interpretations of nowhere dense graphs) in terms of a game called the Flipper game. Currently there are known two proofs of this characterization – one of them is combinatorial while the other one is based on tools from model theory. Although the proofs are quite involved, in my talk I'll present techniques from the model-theoretical proof in the simplified setting of the Splitter game on nowhere dense classes of graphs. In this way I'll reprove combinatorial characterization of such classes in a purely logical way. This is based on joint work with Jakub Gajarský, Nikolas Mählmann, Rose McCarty, Pierre Ohlmann, Michał Pilipczuk, Sebastian Siebertz, Marek Sokołowski, and Szymon Toruńczyk.

---