Speakers
Description
Pierre Ohlmann, Michał Pilipczuk, Wojciech Przybyszewski and Szymon Toruńczyk
Abstract: We use model-theoretic tools originating from stability theory to derive a result we call the Finitary Substitute Lemma, which intuitively says the following. Suppose we work in a stable graph class $\mathcal{C}$, and using a first-order formula $\varphi$ with parameters we are able to define, in every graph $G\in \mathcal{C}$, a relation $R$ that satisfies some hereditary first-order assertion $\psi$. Then we are able to find a first-order formula $\varphi'$ that has the same property, but additionally is {\em{finitary}}: there is finite bound $k\in \mathbb{N}$ such that in every graph $G\in \mathcal{C}$, different choices of parameters give only at most $k$ different relations $R$ that can be defined using $\varphi'$.
We use the Finitary Substitute Lemma to derive two corollaries about the existence of certain canonical decompositions in classes of well-structured graphs.
-
We prove that in the Splitter game, which characterizes nowhere dense graph classes, and in the Flipper game, which characterizes monadically stable graph classes, there is a winning strategy for Splitter, respectively Flipper, that can be defined in first-order logic from the game history. Thus, the strategy is canonical.
-
We show that for any fixed graph class $\mathcal{C}$ of bounded shrubdepth, there is an $O(n^2)$-time algorithm that given an $n$-vertex graph $G\in \mathcal{C}$, computes in an isomorphism-invariant way a structure $H$ of bounded treedepth in which $G$ can be interpreted. A corollary of this result is an $O(n^2)$-time isomorphism test and canonization algorithm for any fixed class of bounded~shrubdepth.