Pith. sign in

REVIEW 1 major objections 5 minor 2 cited by

Transductions of Graph Classes Admitting Product Structure

T0 review · 1 major / 5 minor · reviewed 2026-08-09 · deepseek-v4-flash

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

Pith's one-line read First-order transductions of product-structure classes have bounded P°-clique-width up to perturbations, excluding 3D grids.

desk verdict Strong technical core, but the proof of the headline P° upgrade (Theorem 3.17) has a real gap. read the letter →

arxiv 2501.18326 v4 pith:2LW3LVKQ submitted 2025-01-30 cs.LO math.CO

Petr Hliněný , Jan Jedelský This is my paper · ORCID
classification cs.LOmath.CO MSC 05C7505C8503C1368R10
keywords productstructurefirst-ordertransductionH-clique-widthP-clique-widthplanargraphs3Dgridstree-widthperturbations
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 proves that any graph class obtainable from a product-structure class by a first-order transduction is, up to bounded perturbations, described by a dense structural invariant called P°-clique-width — a labelled expression over reflexive paths. It thereby gives a structural answer to the question of what first-order logic can build from planar graphs and similar classes. The main payoff is a non-transducibility result: the class of all 3D grids cannot be obtained by any first-order transduction from any class admitting product structure, and in particular not from planar graphs. A second example excludes disjoint unions of 'pinned grids' as well.

What carries the argument

The load-bearing object is H-clique-width, a hereditary dense analogue of product structure: a graph has bounded H-clique-width when it is the value of an (H, ℓ)-expression, in which every vertex carries a parameter vertex from a loop graph H and a colour from [ℓ], and edge addition between two colours creates exactly the edges between vertices whose parameter vertices are adjacent in H. This notion is equivalent to being an induced subgraph of H′⊠M with M of bounded clique-width (Theorem 2.4), so it plays the role of a product structure after transduction. The proof machinery constructs such expressions bottom-up along a tree decomposition of the tree-width factor M: each vertex colour stores a bounded amount of type information about vertices in the still-unprocessed part of M, weak-colouring separators control how many vertices must be remembered, and a proper colouring of the 3r-th power of Q keeps the colour domain bounded because strong locality restricts attention to r-neighbours.

What would settle it

Find a first-order transduction τ and a class C admitting product structure such that τ(C) contains every 3D grid; equivalently, exhibit a strongly r-local formula whose images on graphs Q⊠M (Q of bounded degree, M of bounded tree-width) have unbounded P°-clique-width even after any bounded perturbation. The paper itself shows high-degree factors are dangerous, so any counterexample would have to exploit unbounded degree in the product factor.

Watch

Extended reading notes

Core claim

The central theorem (Theorem 3.17) states: if C admits product structure — every graph of C is a subgraph of the strong product of a path and a graph of bounded tree-width — and τ is a first-order transduction whose output on C is a class of simple graphs, then τ(C) is a perturbation of a class of bounded P°-clique-width, where P° is the class of reflexive closures of paths. The proof is carried out in a more general form (Theorem 3.15) replacing paths by any fixed bounded-degree graph class Q, and it builds on a structural decomposition of transductions into a strongly local part and a bounded perturbation (Theorem 2.5). The hard technical step (Lemma 3.1) constructs a (Q°_r, ℓ)-expression for every strongly r-local interpretation of a 2-coloured spanning subgraph of Q⊠M, with ℓ bounded in terms of r, the quantifier rank, the degree bound, and the tree-width bound. From this characterization the paper derives that 3D grids and a class of pinned-grid unions are not transducible from any product-structure class, and in particular not from planar graphs.

Load-bearing premise

The argument collapses if the cited decomposition of first-order transductions into a strongly local transduction followed by a bounded perturbation were false or produced unbounded perturbations, since the bounded P°-clique-width conclusion is derived from that decomposition and from the bounded-degree condition on the path-like factor.

Editorial extensions

If this is right

  • The class of all 3D grids is not first-order transducible from planar graphs, from any graph class admitting product structure, or from any class of graphs embedded on a fixed surface (Corollary 5.6).
  • Disjoint unions of pinned grids (2D grids with apex vertices attached to mutually distant grid points) form another non-transducible family from any product-structure class (Corollaries 5.10 and 5.11).
  • Every first-order transduction of a product-structure class inherits, up to bounded perturbations, the structure of a bounded P°-clique-width class (Theorem 3.17); for general bounded-degree factors Q the analogous statement holds with Q°-clique-width (Theorem 3.15).
  • Conversely, under a stability assumption, every class that is a perturbation of a bounded stable P°-clique-width class is transducible from a product-structure class (Theorem 4.2), giving a two-way correspondence for stable settings.

Reading between the lines

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

  • Inference: the same proof template should yield further non-transducibility results — any graph family whose every k-perturbation has P°-clique-width growing with the grid size will be excluded from every product-structure class by the same argument.
  • Inference: because the constructive proof needs the product decomposition and the transduction's colouring as input (Remark 3.18), the structural characterization may not translate directly into a model-checking algorithm unless a way to find those inputs from the graph alone is found.
  • Inference: if Conjecture 6.1 holds — the expressions built in the proof are stable — then the characterization collapses to 'transducible from product structure' being exactly 'perturbation of bounded expression-stable P°-clique-width', and that property would be transduction-closed, strengthening the main theorem into an exact logical characterization.
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 / 5 minor

Summary. The paper studies first-order transductions of graph classes that admit product structure, i.e., classes whose members are subgraphs of the strong product of a path and a bounded-tree-width graph. The central advertised result is Theorem 3.17, stating that if C admits product structure and τ is a first-order transduction, then τ(C) is, up to bounded perturbation, a class of bounded P°-clique-width, where P° is the class of reflexive paths. Theorem 3.15 proves a parameterized version in which the parameter graph is an r-th power of a bounded-degree graph. The paper derives two applications: the class of 3D grids, and a class of pinned grids, are not transducible from product-structure classes and in particular not from planar graphs. It also proves a converse direction, Theorem 4.2, under a stability assumption.

Significance. If Theorem 3.17 were established, it would give a dense, hereditary analogue of product structure for first-order transductions, with consequences for the transduction hierarchy and for non-transducibility arguments. The paper's technical core, Lemma 3.1, is a long and detailed inductive proof, and Remark 3.18 usefully records that the construction is algorithmic. Corollaries 5.6 and 5.10 would be elegant applications of the framework. However, the proof of Theorem 3.17 contains a gap in the reduction from P°_r-expressions to P°-expressions, and the advertised general theorem is not proved as written. The 3D-grid corollary is independently proved in reference [18], so that particular consequence survives, but the main structural claim needs repair.

major comments (1)
  1. [Theorem 3.17] The edge-emulation step in the proof of Theorem 3.17 is not correct. In P°_r, parameter vertices p_i and p_j are adjacent whenever |i−j| ≤ r, not only when |i−j| ≡ 0 or 1 (mod 3r). After contracting blocks of length r, the rule '|i−j| ≡ 1 mod 3r or |i−j| ≡ 0 mod 3r' therefore omits legitimate edges. For r = 2, take a (P°_2, ℓ)-expression creating one vertex with parameter p_0 and one vertex with parameter p_2, then adding all edges between their two colors. Since p_0p_2 is an edge of P°_2, the value has one edge. After the contraction p_0,p_1 → q_0 and p_2,p_3 → q_1, the residues are 0 and 2, and |0−2| ≡ 2 mod 6, so the constructed (P°, ℓ′) expression adds no edge. Hence the construction does not preserve the value of the expression. Because Theorem 3.17 is the basis for Corollaries 5.6, 5.10, and 5.11 as derived in the paper, the central claim is not supported by the written proof. The gap appears repairable: allowing residue differences 0, 1, ..., r modulo 3r would emulate every original distance at most r while excluding distances greater than r between vertices in the same or adjacent blocks, but this corrected construction must be stated and verified.
minor comments (5)
  1. [Lemma 3.1 proof] The invariant refers to 'Theorem 3.4' although the colors are prescribed by Definition 3.4; similarly, 'As in Theorem 3.6' and 'Back in Theorem 3.7' should refer to Claims 3.6 and 3.7.
  2. [Theorem 3.15 proof] The reference to 'Theorem 3.16' should be to Claim 3.16, and the proof of Claim 3.16 does not need to be called a theorem.
  3. [Section 5] In the proofs of Claims 5.2 and 5.8, the text refers to 'Theorem 5.2' and 'Theorem 5.8', respectively; these should be claim references.
  4. [Section 1.2] The main technical lemma is called both 'Lemma 3.1' and 'Theorem 3.1' in the introduction; the numbering should be unified.
  5. [Figure 2] The caption says 'illustration of Theorem 2.3' but Theorem 2.3 is a definition; please renumber or rephrase for consistency.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the central derivation is self-contained and relies on external decomposition theorems; self-citations are definitional or non-load-bearing. A possible gap in Theorem 3.17 would be a correctness issue, not circularity.

full rationale

I found no step that reduces by construction to its own inputs. Theorem 3.1 is proved from scratch through a tree-decomposition invariant, using weak coloring numbers and Dreier's type-separation theorem as external inputs; it does not assume the target P-degree-clique-width bound. Theorem 3.15 invokes Nešetřil, Ossona de Mendez, and Siebertz's decomposition of transductions into an immersive transduction plus a perturbation (Theorem 2.5), which is an external result not containing the target statement. Theorem 3.17 is a syntactic conversion between expression classes; whether its contraction step correctly preserves all edges of the expression is a proof-correctness question, not a circularity question. The self-citation [22] supplies the definition of H-clique-width and the parameter-free equivalence in Theorem 2.4, which is used mainly as a definitional bridge in the converse direction and in remarks; it is not an assumption entailing the main theorem. The further self-citation to [22] for monadic independence of strong products of two stars supports a side remark about necessity of bounded degree and is not load-bearing for the positive result. Thus the derivation chain is not circular: the main claim has independent mathematical content and no fitted parameter or renamed input is presented as a prediction. I note for completeness that the skeptical concern about distances 2..r in the Theorem 3.17 contraction, if valid, would be a gap in the written proof rather than a circular reduction, so it does not raise the circularity score.

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

The central claims rest on standard background results in FO logic (Dreier's theorem, type finiteness), cited decomposition theorems for transductions, weak coloring bounds, and the authors' earlier H-clique-width equivalence. No free parameters are fitted.

assumptions (6)
  • domain assumption Theorem 2.5: every non-copying first-order transduction is subsumed by an immersive transduction followed by a perturbation.
    Invoked in the proof of Theorem 3.15 to reduce arbitrary transductions to strongly local interpretations; cited from Nešetřil, Ossona de Mendez, Siebertz [24], not reproved here.
  • standard math Theorem 2.6 (Dreier's compositional type theorem): q-types of tuples can be recovered from g(q,ell)-types of separating subtuples.
    Used in Claim 3.7 to conclude that pairs with identical separator types satisfy the same formulas; cited from Dreier [10].
  • standard math Weak r-coloring number of graphs of tree-width k is at most binom(r+k, k).
    Bound by Grohe et al. [20]; used to bound the domain size of the vertex color functions in Lemma 3.1.
  • domain assumption Theorem 2.4: a simple graph has H-clique-width at most ell iff it is an induced subgraph of H' ⊠ M with M of clique-width at most ell.
    Central structural bridge between products and clique-width; cited from the authors' previous paper [22].
  • domain assumption Theorem 4.1: a stable class of bounded clique-width is exactly a transduction of bounded tree-width.
    Used in the converse Theorem 4.2 to convert stable deparameterized expressions into transductions of bounded tree-width; cited from Nešetřil et al. [23].
  • domain assumption Planar graphs and graphs on fixed surfaces admit (classical) product structure.
    Used to specialize the main theorem to planar graphs; cited from Dujmović et al. [12] and others.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Transductions of Graph Classes Admitting Product Structure." pith.science (2026). https://pith.science/paper/2LW3LVKQ

@misc{pith2026250118326,
  author       = {Pith},
  title        = {Pith review of: Transductions of Graph Classes Admitting Product Structure},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2LW3LVKQ}},
  note         = {Machine review of arXiv:2501.18326}
}
read the original abstract

In a quest to thoroughly understand the first-order transduction hierarchy of hereditary graph classes, some questions in particular stand out; such as, what properties hold for graph classes that are first-order transductions of planar graphs (and of similar classes)? When addressing this (so-far wide open) question, we turn to the concept of a product structure - being a subgraph of the strong product of a path and a graph of bounded tree-width, introduced by Dujmovic et al. [JACM 2020]. Namely, we prove that any graph class which is a first-order transduction of a class admitting such product structure, up to perturbations also meets a structural description generalizing the concept of a product structure in a dense hereditary way - the latter concept being introduced just recently by Hlineny and Jedelsky under the name of H-clique-width [MFCS 2024]. Using this characterization, we show that the class of the 3D grids, as well as a class of certain modifications of 2D grids, are not first-order transducible from classes admitting a product structure, and in particular not from the class of planar graphs.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

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

  1. First-order transducibility among classes of sparse graphs

    cs.LO 2025-05 accept novelty 8.0 of 10

    Treewidth t+1 graphs are not first-order transducible from treewidth t graphs, with analogous separations for Hadwiger number and for treewidth 4 graphs from planar graphs.

  2. Short Paths in the Planar Graph Product Structure Theorem

    math.CO 2025-02 conditional novelty 8.0 of 10

    Every n-vertex planar graph is contained in H ⊠ P ⊠ K_c for some planar H of treewidth 3 and a path P of length O((tw(G)+1)^(1-ε) n^ε).

Reference graph

Works this paper leans on

19 extracted references · 4 canonical work pages · cited by 2 Pith papers

  1. [18]

    27 Saharon Shelah

    URL: https://doi.org/10.48550/arXiv.2501.04166, arXiv:2501.04166, doi:10.48550/ ARXIV.2501.04166. 27 Saharon Shelah. Stability, the f.c.p., and superstability; model theoretic properties of formulas in first order theory.Annals of Mathematical Logic, 3(3),

    arXiv doi:10.48550/arxiv.2501.04166

  2. [1]

    On the complexity of embedding in graph products

    1 Therese Biedl, David Eppstein, and Torsten Ueckerdt. On the complexity of embedding in graph products. In Denis Pankratov, editor,Proceedings of the 35th Canadian Conference on Computational Geometry, CCCG 2023, Montreal, Canada, July 31 - August 4, 2023, pages 77–88,

    work page 2023

  3. [6]

    10 Jan Dreier

    URL: https://doi.org/10.46298/dmtcs.8877,doi:10.46298/DMTCS.8877. 10 Jan Dreier. Lacon- and shrub-decompositions: A new characterization of first-order transductions of bounded expansion classes. In36th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2021, Rome, Italy, June 29 - July 2, 2021, pages 1–13. IEEE, 2021.doi:10.1109/LICS52264.2021....

    arXiv

  4. [8]

    14 Vida Dujmovic, Pat Morin, and David R

    doi:10.37236/11712. 14 Vida Dujmovic, Pat Morin, and David R. Wood. Graph product structure for non-minor-closed classes.J. Comb. Theory, Ser. B, 162:34–67,

    work page doi:10.37236/11712

  5. [12]

    URL:https://doi.org/ 10.48550/arXiv.2501.07558,arXiv:2501.07558,doi:10.48550/ARXIV.2501.07558

    Accepted to LICS’25. URL:https://doi.org/ 10.48550/arXiv.2501.07558,arXiv:2501.07558,doi:10.48550/ARXIV.2501.07558. 19 Robert Ganian, Petr Hliněný, Jaroslav Nešetřil, Jan Obdržálek, and Patrice Ossona de Mendez. Shrub-depth: Capturing height of dense graphs.Log. Methods Comput. Sci., 15(1),

    arXiv doi:10.48550/arxiv.2501.07558

  6. [14]

    1137/22m1540296,doi:10.1137/22M1540296

    URL: https://doi.org/10. 1137/22m1540296,doi:10.1137/22M1540296. 22 Petr Hliněný and Jan Jedelský.H -clique-width and a hereditary analogue of product structure. InMFCS 2024, volume 306 ofLIPIcs, pages 61:1–61:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,

    doi:10.1137/22m1540296 2024

  7. [15]

    Hereditary Graph Product Structure and $\cal H$-clique-width

    Extended version arXiv:2403.16789. 23 Jaroslav Nešetřil, Patrice Ossona de Mendez, Michał Pilipczuk, Roman Rabinovich, and Sebastian Siebertz. Rankwidth meets stability. In Dániel Marx, editor,Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, pages 2014–2033. SIAM, 2021.doi:10.1137/1.9...

    work page Pith review arXiv 2021

  8. [16]

    CSL.2022.31,doi:10.4230/LIPICS.CSL.2022.31

    URL:https://doi.org/10.4230/LIPIcs. CSL.2022.31,doi:10.4230/LIPICS.CSL.2022.31. P. Hliněný and J. Jedelský 31 25 Patrice Ossona de Mendez, Michał Pilipczuk, and Sebastian Siebertz. Transducing paths in graph classes with unbounded shrubdepth.Eur. J. Comb., 123:103660,

    doi:10.4230/lipics 2022

Show all 19 references
  1. [17]

    26 Michał Pilipczuk

    URL: https://doi.org/10.1016/j.ejc.2022.103660,doi:10.1016/J.EJC.2022.103660. 26 Michał Pilipczuk. Graph classes through the lens of logic.CoRR, abs/2501.04166,

    2022

  2. [1971]

    28 Szymon Toruńczyk

    doi:10.1016/0003-4843(71) 90015-5. 28 Szymon Toruńczyk. Flip-width: Cops and robber on dense graphs. In64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023, Santa Cruz, CA, USA, November 6-9, 2023, pages 663–700. IEEE, 2023.doi:10.1109/FOCS57990.2023.00045....

    2023

  3. [1990]

    8 Bruno Courcelle, Johann A

    URL: https://doi.org/10.1007/ BFb0017394,doi:10.1007/BFB0017394. 8 Bruno Courcelle, Johann A. Makowsky, and Udi Rotics. Linear time solvable optimization problems on graphs of bounded clique-width.Theory Comput. Syst., 33(2):125–150,

    doi

  4. [2000]

    9 Marc Distel, Robert Hickingbotham, Tony Huynh, and David R

    URL:https://doi.org/10.1007/s002249910009,doi:10.1007/S002249910009. 9 Marc Distel, Robert Hickingbotham, Tony Huynh, and David R. Wood. Improved product structure for graphs on surfaces.Discret. Math. Theor. Comput. Sci., 24(2),

    doi

  5. [2019]

    20 Martin Grohe, Stephan Kreutzer, Roman Rabinovich, Sebastian Siebertz, and Konstantinos S

    doi:10.23638/LMCS-15(1:7)2019. 20 Martin Grohe, Stephan Kreutzer, Roman Rabinovich, Sebastian Siebertz, and Konstantinos S. Stavropoulos. Colouring and covering nowhere dense graphs. In Ernst W. Mayr, editor, Graph-Theoretic Concepts in Computer Science - 41st International Wo...

    2019 doi

  6. [2020]

    13 Vida Dujmovic, Gwenaël Joret, Piotr Micek, Pat Morin, and David R

    doi: 10.1145/3385731. 13 Vida Dujmovic, Gwenaël Joret, Piotr Micek, Pat Morin, and David R. Wood. Bounded-degree planar graphs do not have bounded-degree product structure.Electron. J. Comb., 31(2),

    doi

  7. [2021]

    16 Jakub Gajarský, Jeremi Gładkowski, Jan Jedelský, Michał Pilipczuk, and Szymon Toruńczyk

    Springer International Publishing. 16 Jakub Gajarský, Jeremi Gładkowski, Jan Jedelský, Michał Pilipczuk, and Szymon Toruńczyk. First-order transducibility among classes of sparse graphs.CoRR, abs/2505.15655,

    arXiv

  8. [2022]

    org/10.48550/arXiv.2208.14412,arXiv:2208.14412,doi:10.48550/ARXIV.2208.14412

    URL:https://doi. org/10.48550/arXiv.2208.14412,arXiv:2208.14412,doi:10.48550/ARXIV.2208.14412. 6 Sergio Cabello and Bojan Mohar. Adding one edge to planar graphs makes crossing number and 1-planarity hard.SIAM J. Comput., 42(5):1803–1829, 2013.doi:10.1137/120872310. 7 Bruno Co...

    doi arXiv

  9. [2023]

    2023.03.004,doi:10.1016/J.JCTB.2023.03.004

    URL: https://doi.org/10.1016/j.jctb. 2023.03.004,doi:10.1016/J.JCTB.2023.03.004. 15 Zdenek Dvořák, Tony Huynh, Gwenaël Joret, Chun-Hung Liu, and David R. Wood. Notes on graph product structure theory. In2019-20 MATRIX Annals, pages 513–533, Cham,

    2023 doi

  10. [2024]

    4 Édouard Bonnet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant

    doi:10.1145/3651151. 4 Édouard Bonnet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant. Twin-width I: tractable FO model checking.J. ACM, 69(1):3:1–3:46, 2022.doi:10.1145/3486655. 5 Samuel Braunfeld, Jaroslav Nešetřil, Patrice Ossona de Mendez, and Sebastian Siebertz. On fi...

    2022 arXiv

  11. [2025]

    17 Jakub Gajarský, Petr Hliněný, Jan Obdržálek, Daniel Lokshtanov, and M

    arXiv:2505.15655,doi:10.48550/ARXIV.2505.15655. 17 Jakub Gajarský, Petr Hliněný, Jan Obdržálek, Daniel Lokshtanov, and M. S. Ramanujan. A new perspective on FO model checking of dense graph classes.ACM Trans. Comput. Log., 21(4):28:1–28:23, 2020.doi:10.1145/3383206. 18 Jakub G...

    doi arXiv

Pith tools

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