Proving combinatorial properties of graphs using model theory

A pinnacle of sparsity theory, initiated by Nešetřil and Ossona de Mendez, 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 [Gajarský et al. , arXiv: 2301. 13735]. The interesting thing is that the paper presents two different proofs of the characterization – one is a direct combinatorial proof, while the other one relies on tools from ("infinite") model theory. There is also a notion of a canonical strategy in the Flipper game [Gajarský et al. , arXiv: 2303. 01473]. This time, the only presented proof uses tools from model theory and it is not obvious how to reprove the result in a combinatorial way. In my talk I'll present a simplified version of this result. Namely, I'll sketch a model theoretic proof that in nowhere dense classes of graphs there are at most a constant number of progressing moves for Splitter in the Splitter game. Although this is a purely combinatorial theorem, the only proof we know (so the one I'll sketch) relies on the compactness theorem for first-order logic. Contributed talk given by Wojciech Przybyszewski

Authors

• Wojciech Przybyszewski

Keywords

No keywords are indexed for this paper.