Abstract
We use modeltheoretic 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 ๐, and using a firstorder formula ฯ with parameters we are able to define, in every graph G โ ๐, a relation R that satisfies some hereditary firstorder assertion ฯ. Then we are able to find a firstorder formula ฯ' that has the same property, but additionally is finitary: there is finite bound k โ โ such that in every graph G โ ๐, different choices of parameters give only at most k different relations R that can be defined using ฯ'.
We use the Finitary Substitute Lemma to derive two corollaries about the existence of certain canonical decompositions in classes of wellstructured 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 firstorder logic from the game history. Thus, the strategy is canonical.
 We show that for any fixed graph class ๐ of bounded shrubdepth, there is an ๐ช(nยฒ)time algorithm that given an nvertex graph G โ ๐, computes in an isomorphisminvariant way a structure H of bounded treedepth in which G can be interpreted. A corollary of this result is an ๐ช(nยฒ)time isomorphism test and canonization algorithm for any fixed class of bounded shrubdepth.
BibTeX  Entry
@InProceedings{ohlmann_et_al:LIPIcs.ICALP.2023.135,
author = {Ohlmann, Pierre and Pilipczuk, Micha{\l} and Przybyszewski, Wojciech and Toru\'{n}czyk, Szymon},
title = {{Canonical Decompositions in Monadically Stable and Bounded Shrubdepth Graph Classes}},
booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
pages = {135:1135:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772785},
ISSN = {18688969},
year = {2023},
volume = {261},
editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18187},
URN = {urn:nbn:de:0030drops181874},
doi = {10.4230/LIPIcs.ICALP.2023.135},
annote = {Keywords: Model Theory, Stability Theory, Shrubdepth, Nowhere Dense, Monadically Stable}
}
Keywords: 

Model Theory, Stability Theory, Shrubdepth, Nowhere Dense, Monadically Stable 
Collection: 

50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) 
Issue Date: 

2023 
Date of publication: 

05.07.2023 