8 papers
Flips and Merge-Width in Sparse Graphs
Karolina Drabik, Maël Dumas, Nikolas Mählmann +2
A flip of a graph is obtained by complementing the edge relation within a set of vertices. Flips are typically used to separate vertices in a graph, by increasing the distances bet…
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…
Separability Properties of Monadically Dependent Graph Classes
Édouard Bonnet, Samuel Braunfeld, Ioannis Eleftheriadis +5
A graph class is monadically dependent if one cannot interpret all graphs in colored graphs from using a fixed first-order interpretation. We prove that m…
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…