Pith. sign in

REVIEW 1 major objections 2 minor 1 cited by

Forbidden Induced Subgraphs for Bounded Shrub-Depth and the Expressive Power of MSO

T0 review · 1 major / 2 minor · reviewed 2026-08-10 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read For hereditary graph classes, this paper proves that bounded shrub-depth is equivalent to MSO-stability and to FO and MSO having the same expressive power, via a forbidden-induced-subgraph characterization.

desk verdict Main characterization likely correct and important, but Lemma 6.10 is false as stated and the nibble-based proof of Lemma 6.9 needs replacing. read the letter →

arxiv 2501.13903 v1 pith:MIK26GRY submitted 2025-01-23 cs.LO cs.DMmath.COmath.LO

Nikolas Mählmann This is my paper · ORCID
classification cs.LOcs.DMmath.COmath.LO MSC 03C4505C7568Q1903B70
keywords forbiddeninducedsubgraphsshrub-depthMSO-stabilitymonadicstabilityFOandMSOexpressivepowerflip-flatnesshalf-graphsFO-interpretations
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper establishes a sharp dividing line for hereditary graph classes: bounded shrub-depth is equivalent to a cluster of logical properties, including MSO-stability, CMSO-stability, and equality of expressive power between first-order logic and monadic second-order logic. The new combinatorial core is a forbidden induced subgraph characterization: a hereditary class has unbounded shrub-depth exactly when it contains arbitrarily large flipped half-graphs or flipped disjoint unions of many paths. Combined with an earlier result that FO and MSO coincide on bounded shrub-depth classes, this fully answers the question of which hereditary classes have the same FO and MSO theories. It also strengthens a known result by showing that every hereditary class of unbounded shrub-depth FO-interprets the class of all paths.

What carries the argument

The load-bearing objects are flipped half-graphs and flipped tP_t: graphs obtained from half-graphs or from disjoint unions of t-vertex paths by complementing edges between parts of a fixed vertex partition. The proof proceeds through ∞-flip-flatness, the property that every sufficiently large vertex set contains a large subset that can be made pairwisely disconnected by a bounded number of flips. A technical engine is the uniqueness of irreducible flip-witnesses, which lets the construction detect which edges were flipped and undo them; this yields a single FO-interpretation that recovers all paths from any hereditary class containing arbitrarily large flipped patterns.

What would settle it

Exhibit a hereditary graph class that, for some fixed t, contains no induced flipped half-graph H_t and no induced flipped tP_t, yet has unbounded shrub-depth; Theorem 1.6 says no such class exists. Equivalently, find a hereditary class of unbounded shrub-depth on which FO and MSO define exactly the same sentences, contradicting Theorem 1.9.

Watch

Extended reading notes

Core claim

The paper claims Theorem 1.1: for every hereditary graph class C, bounded shrub-depth is equivalent to excluding all flipped half-graphs of a fixed order and all flipped tP_t; to MSO-stability, monadic MSO-stability, CMSO-stability, and monadic CMSO-stability; to not 1-dimensionally FO-interpreting the class of all paths; and to FO and MSO having the same expressive power on C. The central new step is showing that any class containing arbitrarily large flipped half-graphs or flipped tP_t can FO-interpret all paths, and conversely that any class avoiding these patterns is ∞-flip-flat, hence of bounded shrub-depth.

Load-bearing premise

The argument treats as a black box the prior theorem that a class has bounded shrub-depth exactly when every sufficiently large vertex set contains a large subset that can be made pairwisely disconnected by a bounded number of flips; if that theorem is flawed, the new equivalences no longer follow even if every new lemma is correct.

Editorial extensions

If this is right

  • On every hereditary class of bounded shrub-depth, FO and MSO have exactly the same expressive power, and on every hereditary class of unbounded shrub-depth, MSO is strictly more expressive than FO.
  • For hereditary graph classes, MSO-stability, monadic MSO-stability, CMSO-stability, and monadic CMSO-stability all coincide with bounded shrub-depth.
  • Every hereditary class of unbounded shrub-depth 1-dimensionally FO-interprets the class of all paths, improving the earlier FO-transduction result.
  • For monotone graph classes, MSO-stability coincides with bounded tree-depth.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Editorial inference: the uniform interpretation constructed in Proposition 4.1 suggests that lower bounds or inexpressibility results proved for paths may transfer automatically to every hereditary class of unbounded shrub-depth, without needing to know the class's specific structure.
  • Editorial inference: the 3P_t variant raises a natural testable next step: determine whether replacing 3P_t by 2P_t still characterizes bounded shrub-depth, or whether 2P_t already allows unbounded shrub-depth.
  • Editorial inference: the dependence analog stated in the appendix points toward a possible clique-width or rank-width characterization of MSO-dependence in hereditary classes, a direction the paper raises as a conjecture rather than a proved theorem.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

1 major / 2 minor

Summary. The paper characterizes hereditary graph classes of bounded shrub-depth by explicit forbidden induced subgraphs: for some t, all flipped half-graphs H_t and all flipped tP_t (or equivalently flipped 3P_t) are excluded. From this it derives a chain of equivalences with MSO-stability, monadic CMSO-stability, failure to 1-dimensionally FO-interpret the class of all paths, and equality of the expressive power of FO and MSO. The proof strategy goes through flip-flatness: pattern-free classes are shown to be ∞-flip-flat using the author's earlier stability/flatness characterizations, and classes with unbounded shrub-depth are shown to FO-interpret all paths. The FO/MSO separation is proved separately for flipped half-graphs and for flipped tP_t, using pairs of 'nibbled' graphs that are claimed to be FO-indistinguishable but MSO-distinguishable.

Significance. If correct, Theorem 1.1 would resolve the Elberfeld–Grohe–Tantau question on hereditary classes where FO and MSO coincide, confirm a conjecture of Gajarský and Hliněný, and give the first explicit forbidden-induced-subgraph characterization of bounded shrub-depth. The strengthening from FO-transductions to 1-dimensional FO-interpretations in Theorem 1.7 is a substantial improvement over prior work. The paper is carefully written and the main non-structure arguments are largely self-contained, with explicit interpretations and locality arguments. However, the proof contains a false central lemma in Section 6.3, so the claimed separation of FO and MSO on classes containing flipped tP_t is not established as submitted; this affects Theorem 1.9 and item 9 of Theorem 1.1.

major comments (1)
  1. [Section 6.3, Lemma 6.10] Lemma 6.10 is false as stated. Take q=1, t=3, m=2, and G=2P_3 with no flips. Then nibble1(G) is P_1 ∪ P_3, while nibble2(G) is 2P_2; the FO_1 sentence ∃x∀y¬E(x,y) holds in the former and fails in the latter, contradicting the claimed equality of FO_1 types. The failure is not an isolated edge case: for t=3q, the (3q−1)-balls used in the Hanf argument have different size counts in G+1 and G+2, because G+1 has a P_t component while G+2 has only two P_{t−1} components. In the proof's bijection f, for example with q=2 and t=9, the ball of radius 5 at (1,4) in G+1 has 7 vertices, while its image (2,4) in G+2 has 8 vertices, so f does not preserve ball isomorphism types. Since Lemma 6.9 chooses t=3q and relies on Lemma 6.10 to equate the FO_q types of the two nibbles, the proof of Lemma 6.9, and hence the flipped-tP_t case of Proposition 6.1, is incomplete. A repair may be possible by taking t≥6q+1 and moving the swap threshold to 3q+1, but the statement and proof as written are incorrect.
minor comments (2)
  1. [Section 4.2, Lemma 4.9] In the definition of δ2(x), the formula quantifies y3 and y4 but then refers to twins(y1,y2), which is outside the scope of those quantifiers; it should read twins(y3,y4).
  2. [Section 3.2, Proposition 3.1] The definition of M∞(m) appears to contain a typo: it is written as M_{2t}(max(2m, 2k_t^{2t}·t)), but the application of Corollary 3.11 to the k_{2t}-flip H requires the quantity 2k_{2t}^t·t. Please replace k_t^{2t} with k_{2t}^t and check the exponent against the statement of Corollary 3.11.

Circularity Check

0 steps flagged · score 1.0 of 10

No meaningful circularity: the new characterizations are derived from first principles, with prior flip-flatness theorems used as legitimate external support.

full rationale

The central derivation chain is not circular. The new forbidden-subgraph results are proven directly: Proposition 3.1 gives a combinatorial proof that pattern-free classes are ∞-flip-flat, and the reverse direction is derived from SC-depth lemmas; the bridge ∞-flip-flat ⇔ bounded shrub-depth is cited as Theorem 2.11 from [13,14]. That theorem is a parameter-free classification result whose stated assumptions do not include Theorem 1.1, so it counts as independent support rather than a self-imported conclusion. Similarly, Theorem 3.4 from [11] is a published characterization of monadic FO-stability, and Theorem 2.9 from [20] is an external equivalence between SC-depth and shrub-depth; neither is derived from the paper's target statement. The bounded-shrub-depth ⇒ monadically CMSO-stable direction uses [21] plus Lemma 5.3, whose appendix proof is based on Simon's theorem and compactness, not on the paper's conclusion. The converse directions construct explicit FO-interpretations and FO-transductions (Propositions 4.1 and 4.10) and do not fit any parameter to the target property. No equation in the paper is defined in terms of its own conclusion, and no fitted parameter is renamed as a prediction. I therefore find no significant circularity; the score of 1 merely acknowledges the same-group provenance of the main flatness bridge, which is not load-bearing circularity under the review rules. Separately, there is a serious correctness risk in Lemma 6.10: for q=1, t=3, m=2, and G=2P_3, nibble1(G) has an isolated vertex while nibble2(G) does not, so the claimed FO_1-type equality fails. The proof's bijection does not preserve (3q−1)-balls in this case. This flaw is load-bearing for Lemma 6.9, but it is a proof error, not circularity.

Assumptions & free parameters 0 free parameters · 7 assumptions · 0 invented entities

No fitted constants or invented entities appear. The theorems are proved by combinatorial construction on top of standard finite model theory and published structural graph theory results. The most delicate dependency is Theorem 2.11, which the paper uses to translate between flip-flatness and shrub-depth or stability; it comes from the same research group and is not re-proved here.

assumptions (7)
  • standard math Theorem 2.11: C has bounded shrub-depth iff C is infinity-flip-flat; and C is FO-stable iff C is r-flip-flat for every r.
    Invoked in Sections 3.1 and 3.2; proven in [13] and [14], not re-derived here.
  • standard math Theorem 2.9: bounded SC-depth iff bounded shrub-depth.
    Used in the reverse-direction sketch in Section 3; from [20].
  • standard math Theorem 3.4: monadic FO-stability is characterized by forbidding flipped star/clique r-crossings and flipped half-graphs.
    Used to prove Lemma 3.6 and Proposition 3.9; from [11] as cited via [28].
  • standard math Corollary 6.15, finite Hanf locality: matching counts of (3q-1)-balls implies equal FO_q types.
    Used in the proof of Lemma 6.10; from [16,27].
  • standard math Compactness theorem and Simon's bipartite order-property collapse to singleton variables, Theorem A.1.
    Used in Appendix A to prove Lemma 5.3; from [36] and standard model theory.
  • standard math Lemma 2.2: MSO- and CMSO-interpretations can be pulled back to the source class.
    Used throughout Section 6 to lift inexpressibility results; from [9].
  • domain assumption Graphs are finite, simple, and loopless, and MSO means MSO1 with vertex-set quantification.
    This is the formal setting stated in Section 2.1 and used throughout; different semantics would change the expressiveness claims.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Forbidden Induced Subgraphs for Bounded Shrub-Depth and the Expressive Power of MSO." pith.science (2026). https://pith.science/paper/MIK26GRY

@misc{pith2026250113903,
  author       = {Pith},
  title        = {Pith review of: Forbidden Induced Subgraphs for Bounded Shrub-Depth and the Expressive Power of MSO},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/MIK26GRY}},
  note         = {Machine review of arXiv:2501.13903}
}
read the original abstract

The graph parameter shrub-depth is a dense analog of tree-depth. We characterize classes of bounded shrub-depth by forbidden induced subgraphs. The obstructions are well-controlled flips of large half-graphs and of disjoint unions of many long paths. Applying this characterization, we show that on every hereditary class of unbounded shrub-depth, MSO is more expressive than FO. This confirms a conjecture of [Gajarsk\'y and Hlin\v{e}n\'y; LMCS 2015] who proved that on classes of bounded shrub-depth FO and MSO have the same expressive power. Combined, the two results fully characterize the hereditary classes on which FO and MSO coincide, answering an open question by [Elberfeld, Grohe, and Tantau; LICS 2012]. Our work is inspired by the notion of stability from model theory. A graph class C is MSO-stable, if no MSO-formula can define arbitrarily long linear orders in graphs from C. We show that a hereditary graph class is MSO-stable if and only if it has bounded shrub-depth. As a key ingredient, we prove that every hereditary class of unbounded shrub-depth FO-interprets the class of all paths. This improves upon a result of [Ossona de Mendez, Pilipczuk, and Siebertz; Eur. J. Comb. 2025] who showed the same statement for FO-transductions instead of FO-interpretations.

Figures

Figures reproduced from arXiv: 2501.13903 by the authors.

Figure 1
Figure 1. On the left: the half-graph of order 4 (denoted as [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. A flipped 3P8. More precisely the depicted graph is an L-flip of 3P8 with L = {L1, . . . , L8}, where the following parts were flipped: L2 with L3 (red), L4 with L7 (blue), L7 with L7 (purple). Definition 1.5. The half-graph of order t (denoted as Ht) is the graph on vertices a1, . . . , at and b1, . . . , bt where ai and bj are adjacent if and only if i ⩽ j. A flipped Ht is an {A, B}-flip of Ht , where the flip-par… view at source ↗
Figure 3
Figure 3. All flipped H4s (up to isomorphism). Figure replicated with permission from [28, [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗
Figures from the paper (8 more)
Figure 4
Figure 4. Figure 4: A map of Theorem 1.1: combinatorial and logical characterizations of hereditary classes of bounded [PITH_FULL_IMAGE:figures/full_fig_p007_4.png]
Figure 5
Figure 5. Figure 5: From left to right: the star 4-crossing of order 3, the clique 4-crossing of order 3, and the rook [PITH_FULL_IMAGE:figures/full_fig_p012_5.png]
Figure 6
Figure 6. Figure 6: The two cases from Lemma 3.10. The circles are the layering of a BFS tree around the vertices of [PITH_FULL_IMAGE:figures/full_fig_p014_6.png]
Figure 7
Figure 7. Figure 7: On the left: An enumeration of all flipped 2 [PITH_FULL_IMAGE:figures/full_fig_p015_7.png]
Figure 8
Figure 8. Figure 8: The induced subgraph of a flipped 5P8 in which the interpretation I can interpret P8. In this example the following layers were flipped: L2 with L3 (red), L4 with L7 (blue), L7 with L7 (purple). Proof of Lemma 4.4. By assumption C contains a graph H′ that is an L-flip …
Figure 9
Figure 9. Figure 9: The graph G from the proof of Lemma 4.9 for t = 4. It is an induced subgraph of a flipped Ht+3. In this example, the set A is flipped with itself, which is the reason why there is a clique on the A vertices. 4.3 Wrapping Up the Interpretation We are now ready to prove …
Figure 10
Figure 10. Figure 10: H⋆ 4 together with a partitioning of its vertex set by the domain formulas. 20 [PITH_FULL_IMAGE:figures/full_fig_p022_10.png]
Figure 11
Figure 11. Figure 11: An illustration of the case q = 2, m = 3, t = 9 ⩾ 3 q . Depicted are the t-colored graphs G + 1 and G + 2 . The bijection f : V (G + 1 ) → V (G + 2 ) is drawn between the two graphs, where we have omitted the mapping arrows for vertices (i, j) from G + 1 that are mapp…

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Unavoidable pivot-minors in graphs of large rank-depth

    math.CO 2025-07 conditional novelty 7.0 of 10

    Every graph of large rank-depth contains a pivot-minor isomorphic to a long path or to two cliques joined by a half-graph, resolving a 2021 conjecture.

Reference graph

Works this paper leans on

37 extracted references · 32 canonical work pages · cited by 1 Pith paper

  1. [11]

    First-Order Model Checking on Monadically Stable Graph Classes

    Jan Dreier, Ioannis Eleftheriadis, Nikolas M¨ ahlmann, Rose McCarty, Micha l Pilipczuk, and Szymon Toru´ nczyk. First-Order Model Checking on Monadically Stable Graph Classes . In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS) , pages 21–30, Los Alamitos, CA, USA, October 2024. IEEE Computer Society

    work page 2024

  2. [1]

    Interpreting nowhere dense graph classes as a classical notion of model theory

    Hans Adler and Isolde Adler. Interpreting nowhere dense graph classes as a classical notion of model theory. European Journal of Combinatorics , 36:322–330, 2014

    2014

  3. [2]

    Tree-decomposable theories

    Peter John Anderson. Tree-decomposable theories. Master’s thesis, Simon Fraser University, 1990

    work page 1990

  4. [3]

    Baldwin and Saharon Shelah

    John T. Baldwin and Saharon Shelah. Second-order quantifiers and the complexity of theories. Notre Dame Journal of Formal Logic , 26(3):229–303, 1985

    work page 1985

  5. [4]

    Separator logic and star-free expressions for graphs

    Mikolaj Bojanczyk. Separator logic and star-free expressions for graphs. arXiv preprint arXiv:2107.13953, 2021

    arXiv 2021

  6. [5]

    Model checking on interpretations of classes of bounded local cliquewidth

    ´Edouard Bonnet, Jan Dreier, Jakub Gajarsk´ y, Stephan Kreutzer, Nikolas M¨ ahlmann, Pierre Simon, and Szymon Toru´ nczyk. Model checking on interpretations of classes of bounded local cliquewidth. In Christel Baier and Dana Fisman, editors, LICS ’22: 37th Annual ACM/IEEE Symposium on Logic in Computer Science, Haifa, Israel, August 2 - 5, 2022 , pages 54...

    work page 2022

  7. [6]

    Twin-width iv: Ordered graphs and matrices

    ´Edouard Bonnet, Ugo Giocanti, Patrice Ossona de Mendez, Pierre Simon, St´ ephan Thomass´ e, and Szymon Toru´ nczyk. Twin-width iv: Ordered graphs and matrices. J. ACM, 71(3), jun 2024

    work page 2024

  8. [7]

    Laskowski

    Samuel Braunfeld and Michael C. Laskowski. Existential characterizations of monadic nip. arXiv preprint arXiv:2209.05120 , 2022

    arXiv 2022

Show all 37 references
  1. [8]

    Shallow vertex minors, stability, and dependence

    Hector Buffi` ere, Eun Jung Kim, and Patrice Ossona de Mendez. Shallow vertex minors, stability, and dependence. Innovations in Graph Theory , 1:87–112, 2024

    2024

  2. [9]

    Graph structure and monadic second-order logic: a language-theoretic approach, volume 138

    Bruno Courcelle and Joost Engelfriet. Graph structure and monadic second-order logic: a language-theoretic approach, volume 138. Cambridge University Press, 2012

    2012

  3. [10]

    Vertex-minors, monadic second-order logic, and a conjecture by Seese

    Bruno Courcelle and Sang-il Oum. Vertex-minors, monadic second-order logic, and a conjecture by Seese. Journal of Combinatorial Theory, Series B , 97(1):91–126, 2007

    2007

  4. [12]

    First-order model checking on struc- turally sparse graph classes

    Jan Dreier, Nikolas M¨ ahlmann, and Sebastian Siebertz. First-order model checking on struc- turally sparse graph classes. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, pages 567–580, New York, NY, USA, 2023. Association for Computing Machinery

    2023

  5. [13]

    Indiscernibles and flatness in monadically stable and monadically NIP classes

    Jan Dreier, Nikolas M¨ ahlmann, Sebastian Siebertz, and Szymon Toru´ nczyk. Indiscernibles and flatness in monadically stable and monadically NIP classes. In Kousha Etessami, Uriel Feige, and Gabriele Puppis, editors, 50th International Colloquium on Automata, Languages, and P...

    2023

  6. [14]

    Flip-breakability: A combinatorial dichotomy for monadically dependent graph classes

    Jan Dreier, Nikolas M¨ ahlmann, and Szymon Toru´ nczyk. Flip-breakability: A combinatorial dichotomy for monadically dependent graph classes. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing , STOC 2024, page 1550–1560, New York, NY, USA, 2024. Associatio...

    2024

  7. [15]

    Where first-order and monadic second-order logic coincide

    Michael Elberfeld, Martin Grohe, and Till Tantau. Where first-order and monadic second-order logic coincide. ACM Trans. Comput. Logic, 17(4), September 2016

    2016

  8. [16]

    Stockmeyer, and Moshe Y

    Ronald Fagin, Larry J. Stockmeyer, and Moshe Y. Vardi. On monadic np vs monadic co-np. Information and Computation , 120(1):78–92, 1995

    1995

  9. [17]

    On local and non-local properties

    Haim Gaifman. On local and non-local properties. In Proceedings of the Herbrand Symposium, volume 107 of Stud. Logic Found. Math. , pages 105 – 135. Elsevier, 1982

    1982

  10. [18]

    Kernelizing mso properties of trees of fixed height, and some consequences

    Jakub Gajarsk´ y and Petr Hlinˇ en´ y. Kernelizing mso properties of trees of fixed height, and some consequences. Logical Methods in Computer Science , Volume 11, Issue 1, Apr 2015

    2015

  11. [19]

    Flipper Games for Monadically Stable Graph Classes

    Jakub Gajarsk´ y, Nikolas M¨ ahlmann, Rose McCarty, Pierre Ohlmann, Micha l Pilipczuk, Woj- ciech Przybyszewski, Sebastian Siebertz, Marek Soko lowski, and Szymon Toru´ nczyk. Flipper Games for Monadically Stable Graph Classes. In Kousha Etessami, Uriel Feige, and Gabriele Pup...

    2023

  12. [20]

    When trees grow low: Shrubs and fast MSO1

    Robert Ganian, Petr Hlinˇ en´ y, Jaroslav Neˇ setˇ ril, Jan Obdrˇ z´ alek, Patrice Ossona de Mendez, and Reshma Ramadurai. When trees grow low: Shrubs and fast MSO1. In Branislav Rovan, Vladimiro Sassone, and Peter Widmayer, editors, Mathematical Foundations of Computer Scienc...

    2012

  13. [21]

    Shrub-depth: Capturing height of dense graphs

    Robert Ganian, Petr Hlinˇ en´ y, Jaroslav Nesetril, Jan Obdrz´ alek, and Patrice Ossona de Mendez. Shrub-depth: Capturing height of dense graphs. Log. Methods Comput. Sci. , 15(1), 2019

    2019

  14. [22]

    Deciding first-order properties of nowhere dense graphs

    Martin Grohe, Stephan Kreutzer, and Sebastian Siebertz. Deciding first-order properties of nowhere dense graphs. Journal of the ACM (JACM) , 64(3):1–32, 2017

    2017

  15. [23]

    Model-theoretic methods in the study of elementary logic

    William Hanf. Model-theoretic methods in the study of elementary logic. In The Theory of Models, Studies in Logic and the Foundations of Mathematics, pages 132–145. North-Holland, 1965

    1965

  16. [24]

    A Shorter Model Theory

    Wilfrid Hodges. A Shorter Model Theory . Cambridge University Press, 1997

    1997

  17. [25]

    Obstructions for bounded shrub-depth and rank-depth

    O-joung Kwon, Rose McCarty, Sang il Oum, and Paul Wollan. Obstructions for bounded shrub-depth and rank-depth. Journal of Combinatorial Theory, Series B , 149:76–91, 2021

    2021

  18. [26]

    Model checking lower bounds for simple graphs

    Michael Lampis. Model checking lower bounds for simple graphs. Logical Methods in Computer Science, Volume 10, Issue 1, Mar 2014

    2014

  19. [27]

    Elements of finite model theory , volume 41

    Leonid Libkin. Elements of finite model theory , volume 41. Springer, 2004

    2004

  20. [28]

    PhD thesis, University of Bremen, 2024

    Nikolas M¨ ahlmann.Monadically Stable and Monadically Dependent Graph Classes: Character- izations and Algorithmic Meta-Theorems . PhD thesis, University of Bremen, 2024. 26

    2024

  21. [29]

    Makowsky

    Johann A. Makowsky. Algorithmic uses of the feferman–vaught theorem. Annals of Pure and Applied Logic, 126(1):159–213, 2004. Provinces of logic determined. Essays in the memory of Alfred Tarski. Parts I, II and III

    2004

  22. [30]

    On nowhere dense graphs.European Journal of Combinatorics , 32(4):600–617, 2011

    Jaroslav Neˇ setˇ ril and Patrice Ossona de Mendez. On nowhere dense graphs.European Journal of Combinatorics , 32(4):600–617, 2011

    2011

  23. [31]

    Canonical Decompositions in Monadically Stable and Bounded Shrubdepth Graph Classes

    Pierre Ohlmann, Micha l Pilipczuk, Wojciech Przybyszewski, and Szymon Toru´ nczyk. Canonical Decompositions in Monadically Stable and Bounded Shrubdepth Graph Classes. In Kousha Etessami, Uriel Feige, and Gabriele Puppis, editors, 50th International Colloquium on Automata, Lan...

    2023

  24. [32]

    Transducing paths in graph classes with unbounded shrubdepth

    Patrice Ossona de Mendez, Micha l Pilipczuk, and Sebastian Siebertz. Transducing paths in graph classes with unbounded shrubdepth. European Journal of Combinatorics , 123:103660,

  25. [33]

    Stable graphs.Fundamenta Mathematicae, 100(2):101– 107, 1978

    Klaus-Peter Podewski and Martin Ziegler. Stable graphs.Fundamenta Mathematicae, 100(2):101– 107, 1978

    1978

  26. [34]

    First-order logic with connec- tivity operators

    Nicole Schirrmacher, Sebastian Siebertz, and Alexandre Vigny. First-order logic with connec- tivity operators. ACM Trans. Comput. Logic, 24(4), July 2023

    2023

  27. [35]

    The structure of the models of decidable monadic theories of graphs

    Detlef Seese. The structure of the models of decidable monadic theories of graphs. Annals of Pure and Applied Logic , 53(2):169–195, 1991

    1991

  28. [36]

    A note on stability and nip in one variable

    Pierre Simon. A note on stability and nip in one variable. arXiv preprint arXiv:2103.15799 , 2021. 27 A Monadic Stability via Transductions The goal of this section is to prove the following lemma used in Section 5. Lemma 5.3. For every logic L that extends FO and every class ...

    2021 arXiv

  29. [2025]

    SI: Sparsity in Algorithms, Combinatorics and Logic

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.