6 papers · 1 filter
Flipping and Forking
Wojciech Przybyszewski, Szymon Toruńczyk
Monadic stability and the more general monadic dependence (or NIP) are tameness conditions for classes of logical structures, studied in the 80's in Shelah's classification program…
Low rank MSO
Mikołaj Bojańczyk, Michał Pilipczuk, Wojciech Przybyszewski +2
We introduce a new logic for describing properties of graphs, which we call low rank MSO. This is the fragment of monadic second-order logic in which set quantification is restrict…
Canonical decompositions in monadically stable and bounded shrubdepth graph classes
Pierre Ohlmann, Michał Pilipczul, Szymon Toruńczyk +1
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…
Flipper games for monadically stable graph classes
Jakub Gajarský, Nikolas Mählmann, Rose McCarty +6
A class of graphs is monadically stable if for any unary expansion of , one cannot interpret, in first-order logic, arbitrarily l…
Twin-width and types
Jakub Gajarský, Michał Pilipczuk, Wojciech Przybyszewski +1
We study problems connected to first-order logic in graphs of bounded twin-width. Inspired by the approach of Bonnet et al. [FOCS 2020], we introduce a robust methodology of local…
Distal combinatorial tools for graphs of bounded twin-width
Wojciech Przybyszewski
We study set systems formed by neighborhoods in graphs of bounded twin-width. We start by proving that such graphs have linear neighborhood complexity, in analogy to previous resul…