Pith. sign in

REVIEW 6 minor 1 cited by

First-order transducibility among classes of sparse graphs

T0 review · 0 major / 6 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read First-order transducibility among sparse graph classes forces containment in congested shallow minors of the source plus a universal vertex, making the polynomial degree of weak coloring numbers a transduction invariant.

desk verdict A clean proof that weak coloring number degree is a FO-transduction invariant, resolving the treewidth hierarchy question and giving sharp separations. read the letter →

arxiv 2505.15655 v1 pith:MPE3MLPY submitted 2025-05-21 cs.LO cs.DMmath.CO

Jakub Gajarský , Jeremi G{l}adkowski , Jan Jedelský , Micha{l} Pilipczuk , Szymon Toruńczyk This is my paper
classification cs.LOcs.DMmath.CO MSC 03C1305C8368Q19
keywords first-ordertransductionsboundedexpansionweakcoloringnumberstreewidthHadwigernumberplanargraphscongestedshallowminorssparse
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 first-order transducibility is a much more restrictive relation between sparse graph classes than previously known. Its central result is a structural containment: if a weakly sparse class D can be transduced from a class C of bounded expansion, then for some fixed k every graph in D appears as a k-congested depth-k minor of a graph obtained from C by adding a single universal vertex. Feeding known estimates of weak coloring numbers into this containment yields three strictness theorems: treewidth t+1 is not transducible from treewidth t; Hadwiger number t+2 is not transducible from Hadwiger number t; and treewidth 4 is not transducible from planar graphs. The paper thereby turns a model-theoretic question into a finitary graph-minor computation and resolves an open problem about the treewidth hierarchy.

What carries the argument

The load-bearing object is the weak d-coloring number wcol_d(G): the minimum, over vertex orderings, of the maximum size of a vertex's weak d-reachability set — the vertices u such that there is a path of length at most d from v to u whose every vertex is at least u in the ordering. For a graph class C, π_C(d)=wcol_d(C) is a function of d that is a polynomial for all classes considered; its degree is the invariant. Theorem 3.1 is the essential bridge: it shows transducibility of a weakly sparse D from bounded-expansion C forces D ⊆ Minors^k_k(C°), and Lemma 4.1 shows this containment forces π_C to dominate π_D, i.e., the polynomial degree cannot rise. Two auxiliary mechanisms carry the proof of Theorem 3.1: the Local Feferman–Vaught Theorem, which gives a finite color palette determining φ on pairs separated by a small set, and a counting argument based on Ramsey's theorem and a Bollobás-type set lemma that turns the color data into a shallow-minor model with bounded congestion and depth. The universal vertex in C° creates the global intersection of reachability sets needed to apply the local theorem everywhere at once.

What would settle it

Exhibit a weakly sparse class D transducible from a bounded-expansion class C whose weak d-coloring number grows as a polynomial of strictly larger degree than that of C; Corollary 4.2 forbids such a pair, so any example would refute the paper's central invariant.

Watch

Extended reading notes

Core claim

The paper's central claim is Theorem 3.1: letting C° denote the class obtained from C by adjoining a universal vertex, and Minors^k_k(C°) the class of k-congested depth-k minors of members of C°, whenever D is weakly sparse and transducible from a bounded-expansion class C, there is a k with D ⊆ Minors^k_k(C°). The proof runs through a local Feferman–Vaught theorem: for a fixed first-order formula φ and a bounded-size separator, whether φ(u,v) holds is decided by finitely many colors of u and v, provided u and v are sufficiently separated. The universal vertex is exactly what makes every pair of weak d-reachability sets intersect, so the coloring argument applies globally, and a Ramsey plus Bollobás-type counting argument converts the color information into a congested shallow-minor model of the transduced graph. Combined with Lemma 4.1 — which bounds the weak d-coloring number of a k-congested depth-k minor by k times the weak (4k+1)d-coloring number of the host — this yields Corollary 4.2: the polynomial degree (in d) of the weak d-coloring number cannot increase under transduction. Since the treewidth-t class has π(d)=binom(d+t,t), degree t; the Hadwiger-t class has degree between t−1 and t; and planar graphs have degree at most 3 while treewidth-4 has degree 4, the strictness theorems follow by comparing degrees.

Load-bearing premise

The paper's negative results assume the published weak-coloring-number bounds (the binomial formula for treewidth t, the Ω($d^{{t−1}}$)/O(d^t) bounds for Hadwiger classes, and the O($d^{3}$) planar bound); if any of those degrees is wrong, the corresponding separation collapses.

Editorial extensions

If this is right

  • The treewidth hierarchy is strict for first-order transductions: for every t, the class of graphs of treewidth at most t+1 cannot be transduced from the class of graphs of treewidth at most t, settling a question left open by Braunfeld, Nešetřil, Ossona de Mendez, and Siebertz.
  • The Hadwiger-number hierarchy is strict with a gap of two: graphs with Hadwiger number at most t+2 are not transducible from graphs with Hadwiger number at most t.
  • Planar graphs cannot encode all graphs of treewidth 4, despite the fact that every pathwidth-t class is transducible from planar graphs; the boundary sits between treewidth 3 and treewidth 4.
  • Among bounded-expansion classes, transducibility with copying is equivalent to containment in k-congested depth-k minors of the source class augmented by a universal vertex, for some k (Corollary 3.12); this gives a purely combinatorial characterization of the transduction quasi-order on sparse classes.
  • The polynomial degree of the weak d-coloring number is a transduction invariant for sparse classes, so any transduction from C to D forces deg π_D ≤ deg π_C; degree gaps alone produce separation theorems.

Reading between the lines

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

  • If the converse of Corollary 4.2 held in general — that is, if deg π_D ≤ deg π_C implied transducibility for natural sparse classes — the transduction quasi-order on bounded-expansion classes would collapse to a degree ladder; the paper's characterization (Corollary 3.12) suggests such a conjecture is at least plausible for classes closed under the relevant operations, but the paper does not prove
  • The open status of treewidth 3 versus planar graphs becomes a concrete analytic question: improving the planar upper bound from O(d^3) to O(d^2) would, by the same argument, separate treewidth 3 from planar graphs; conversely, any transduction from planar graphs to treewidth 3 would force a quartic lower bound on the planar weak coloring number, contradicting the current cubic upper bound, so the
  • The congested-minor containment of Theorem 3.1 is stated for first-order transductions, but the proof scheme — local Feferman–Vaught plus counting — suggests analogous containment characterizations for extensions of first-order logic (e.g., with counting quantifiers), where locality statements of the same flavor are known; testing this transfer is a natural next step.
  • The necessity of the universal vertex in Theorem 3.1 (stars are transducible from edgeless graphs but are not congested shallow minors of edgeless graphs) shows the invariant is sensitive to the connectivity structure of the source class; for classes that are already connected in the relevant weak-reachability sense, the extra vertex might be avoidable, which would sharpen the containment to plain
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

0 major / 6 minor

Summary. This paper proves three non-transducibility results for first-order transductions among sparse graph classes: treewidth t+1 is not transducible from treewidth t, Hadwiger number t+2 is not transducible from Hadwiger number t, and treewidth 4 is not transducible from planar graphs. The technical core is Theorem 3.1, which shows that if a weakly sparse class D is transducible from a bounded-expansion class C, then for some k every graph in D is a k-congested depth-k minor of a graph from C after adding a universal vertex. The paper then proves Lemma 4.1, showing that the degree (as a polynomial in d) of the weak d-coloring number is preserved under this containment up to constant factors, and applies known upper and lower bounds for weak coloring numbers to obtain the listed separations.

Significance. This is a substantial contribution to the transducibility quasi-order for sparse graphs. It resolves the open question of whether the treewidth hierarchy is strict under first-order transductions and gives a new, easy-to-use invariant (the polynomial degree of the weak coloring number) that also separates treewidth 4 from planar graphs. The proof of Theorem 3.1 is self-contained and detailed: the Local Feferman-Vaught argument, the Bollobás-type counting, the Ramsey-based edge partition, and the congested-shallow-minor model are all carefully verified. The authors are explicit that the final separations depend on published weak-coloring bounds from [8] and [15]; these are standard, and the asymptotic degrees, rather than precise constants, are all that is needed. The paper also offers a characterization of transducibility with copying among bounded-expansion classes as a corollary. Overall the central claim is sound and the presentation is clear.

minor comments (6)
  1. [Claim 3.9] In the congestion bound, the direct term {u} in the definition of η(u) is not counted through the sets X_w. Each vertex v belongs to η(v) in addition to the at most s·f(s,t,|Λ|) sets found via X_w, so the bound should be s·f(s,t,|Λ|)+1. Since the lemma only requires existence of some k, setting k := s·f(s,t,|Λ|)+1 repairs the proof; no theorem statement changes.
  2. [Proof of Claim 3.6] The text sets r = Ramsey(ss, 2t) but then uses 'a clique of size 2t or an independent set of size ss'. The intended value is r = Ramsey(2t, ss), consistent with the definition of f and with the subsequent case analysis.
  3. [Lemma 3.4] The bound is written as b_0 + b_1 + ... + b_a; it should be b^0 + b^1 + ... + b^a. The proof itself is correct.
  4. [Lemma 4.1] In the sentence 'Noting that η(x) and η(y) touch and induce connected graphs of radius at most d', the radius bound should be k (the depth of the congested minor), not d; the subsequent bound (4k+1)d is consistent with radius k.
  5. [Proof of Theorem 3.1] Lemma 3.3 produces a depth-2d model, while the theorem statement requires a depth-k model for the same k. This is a purely formal mismatch: one should take k' = max(k, 2d) (and k' as congestion) to match the statement.
  6. [Section 4, around Eq. (4.1)] There is a typo in 'wcol(4k+1))d(G, ≼)' with an extra parenthesis; also 'letη' should be 'let η'.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the headline separations follow from an internally proved minor-containment theorem combined with published external degree bounds.

full rationale

The paper's central chain is Theorem 3.1 -> Lemma 4.1 -> Corollary 4.2. Theorem 3.1 is proved internally from the Local Feferman-Vaught Theorem (Theorem 3.2, cited to [3,12]), the counting Lemma 3.4, and the construction in Lemma 3.3; it does not presuppose any of the target non-transducibility statements. Lemma 4.1 is an independent pullback argument for weak coloring numbers under k-congested depth-k minors, and Corollary 4.2 follows by composition. The final separations (Theorems 1.1-1.3) then combine Corollary 4.2 with published weak-coloring degree bounds from [8] and [15]. Those bounds are external to the paper; they are not derived from, nor equivalent to, the transducibility conclusions, and the paper explicitly states them as known inputs. The only shared-author citations are [5], [6], [12], and [13]. [5] is cited only for a previously known bounded-expansion consequence, [6] for a related prior result, [13] as a survey, and [12] as a source of the Feferman-Vaught theorem. None is used to force the paper's conclusions: Theorem 3.2 is stated in full and is a standard external theorem, and the weak-coloring estimates are not supplied by the paper itself. No parameter is fitted to a subset of the data and then renamed a prediction, and no graph class is defined in terms of the invariant used to separate it. The minor technical issue in Claim 3.9 that the singleton {u} may add one to the congestion bound is a constant-factor repair and does not affect the existence of some k, so it has no circularity relevance. Overall, the derivation is self-contained modulo standard published bounds, and the non-transducibility claims have independent content.

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

No free parameters are fitted in this paper. The proof relies on published theorems on weak coloring numbers and the Local Feferman-Vaught Theorem. The paper introduces no new entities beyond standard constructions such as universal vertices, congested shallow minors, and weak reachability sets.

assumptions (7)
  • standard math Local Feferman-Vaught Theorem (Theorem 3.2): for every symmetric FO formula phi, there are d and finite Lambda such that phi(u,v) depends only on (lambda(u),lambda(v)) whenever u,v are d-separated by a set S of bounded size.
    Invoked in Claim 3.6 to partition edges by color pairs; if invalid, the construction of the vertex covers X_w in Lemma 3.3 breaks.
  • domain assumption Weak d-coloring number of the class of treewidth-t graphs is exactly binom(d+t,t).
    Used in Theorem 1.1; this degree-t polynomial is the entire separation between T_t and T_{t+1}, cited from [8].
  • domain assumption Weak d-coloring numbers for classes of bounded Hadwiger number t satisfy Omega(d^{t-1}) and O(d^t).
    Used in Theorem 1.2 to show H_t cannot dominate H_{t+2}; cited from [8] and [15].
  • domain assumption Weak d-coloring number of planar graphs is O(d^3) and of treewidth-4 graphs is Omega(d^4).
    Used in Theorem 1.3; cited from [15] and [8].
  • standard math A graph class has bounded expansion iff all weak d-coloring numbers are finite (Theorem 2.3, [16]).
    Used in the proof of Theorem 3.1 to guarantee s = wcol_{2d}(C)+1 is finite.
  • domain assumption For every k and bounded expansion class C', Minors^k(C') is transducible from C' (Claim 3.11, [2, Corollary 7.6]).
    Used in Lemma 3.10 for the converse part of the bounded-expansion characterization; not needed for Theorems 1.1-1.3.
  • standard math The class of bounded expansion is closed under taking k-congested depth-k minors (Theorem 2.2).
    Used in Section 3 remarks and Lemma 3.10 to justify that constructed classes still have bounded expansion.

how reviews work

0 comments
Cite this review

Pith. "Pith review of First-order transducibility among classes of sparse graphs." pith.science (2026). https://pith.science/paper/MPE3MLPY

@misc{pith2026250515655,
  author       = {Pith},
  title        = {Pith review of: First-order transducibility among classes of sparse graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/MPE3MLPY}},
  note         = {Machine review of arXiv:2505.15655}
}
abstract

We prove several negative results about first-order transducibility for classes of sparse graphs: - for every $t \in \mathbb{N}$, the class of graphs of treewidth at most $t+1$ is not transducible from the class of graphs of treewidth at most $t$; - for every $t \in \mathbb{N}$, the class of graphs with Hadwiger number at most $t+2$ is not transducible from the class of graphs with Hadwiger number at most $t$; and - the class of graphs of treewidth at most $4$ is not transducible from the class of planar graphs. These results are obtained by combining the known upper and lower bounds on the weak coloring numbers of the considered graph classes with the following two new observations: - If a weakly sparse graph class $\mathscr D$ is transducible from a class $\mathscr C$ of bounded expansion, then for some $k \in \mathbb{N}$, every graph $G \in \mathscr D$ is a $k$-congested depth-$k$ minor of a graph $H^\circ$ obtained from some $H\in \mathscr C$ by adding a universal vertex. - The operations of adding a universal vertex and of taking $k$-congested depth-$k$ minors, for a fixed $k$, preserve the degree of the distance-$d$ weak coloring number of a graph class, understood as a polynomial in $d$.

Discussion (0). Sign in 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. k-Planar and Fan-Crossing Drawings and Transductions of Embeddable Graphs

    cs.CG 2025-06 conditional novelty 7.0 of 10

    Sparse graph classes are first-order transducible from graphs on a fixed surface if and only if they admit a new type of bounded fan-crossing drawing on that surface.

Reference graph

Works this paper leans on

16 extracted references · 13 canonical work pages · cited by 1 Pith paper

  1. [8]

    Stavropoulos

    Martin Grohe, Stephan Kreutzer, Roman Rabinovich, Sebastian Siebertz, and Konstantinos S. Stavropoulos. Coloring and covering nowhere dense graphs. SIAM Journal on Discrete Mathematics , 32(4):2467–2481, 2018

    work page 2018

  2. [15]

    On the generalised colouring numbers of graphs that exclude a fixed minor

    Jan van den Heuvel, Patrice Ossona de Mendez, Daniel Quiroz, Roman Rabinovich, and Sebastian Siebertz. On the generalised colouring numbers of graphs that exclude a fixed minor. European Journal of Combinatorics, 66:129–144, 2017

    work page 2017

  3. [1]

    Twin-width I: Tractable FO model checking

    ´Edouard Bonnet, Eun Jung Kim, St´ephan Thomass´e, and R´emi Watrigant. Twin-width I: Tractable FO model checking. Journal of the ACM, 69(1):3:1–3:46, 2022

    work page 2022

  4. [2]

    On first-order transductions of classes of graphs

    Samuel Braunfeld, Jaroslav Neˇsetˇril, Patrice Ossona de Mendez, and Sebastian Siebertz. On first-order transductions of classes of graphs. ArXiv preprint, abs/2208.14412, 2022

    arXiv 2022

  5. [3]

    Lacon-, shrub- and parity-decompositions: Characterizing transductions of bounded ex- pansion classes

    Jan Dreier. Lacon-, shrub- and parity-decompositions: Characterizing transductions of bounded ex- pansion classes. Logical Methods in Computer Science , 19(2), 2023

    work page 2023

  6. [4]

    Vida Dujmovi ´c, Gwena¨el Joret, Piotr Micek, Pat Morin, Torsten Ueckerdt, and David R. Wood. Planar graphs have bounded queue-number. Journal of the ACM, 67(4):22:1–22:38, 2020

    work page 2020

  7. [5]

    First-order interpretations of bounded expansion classes

    Jakub Gajarsk ´y, Stephan Kreutzer, Jaroslav Ne ˇsetˇril, Patrice Ossona de Mendez, Michał Pilipczuk, Sebastian Siebertz, and Szymon Toru´nczyk. First-order interpretations of bounded expansion classes. ACM Transactions on Computational Logic , 21(4):29:1–29:41, 2020

    work page 2020

  8. [6]

    3D-grids are not transducible from planar graphs

    Jakub Gajarsk ´y, Michał Pilipczuk, and Filip Pokr ´yvka. 3D-grids are not transducible from planar graphs. ArXiv preprint, abs/2501.07558, 2025. Accepted to LICS 2025

    work page Pith review arXiv 2025

Show all 16 references
  1. [7]

    Shrub- depth: Capturing height of dense graphs

    Robert Ganian, Petr Hlin ˇen´y, Jaroslav Neˇsetˇril, Jan Obdrˇz´alek, and Patrice Ossona de Mendez. Shrub- depth: Capturing height of dense graphs. Logical Methods in Computer Science , 15(1), 2019

    2019

  2. [9]

    Transductions of graph classes admitting product structure

    Petr Hlin ˇen´y and Jan Jedelsk ´y. Transductions of graph classes admitting product structure. ArXiv preprint, abs/2501.18326, 2025. Accepted to LICS 2025

    2025 arXiv

  3. [10]

    Sparsity — Graphs, Structures, and Algorithms , vol- ume 28 of Algorithms and combinatorics

    Jaroslav Ne ˇsetˇril and Patrice Ossona de Mendez. Sparsity — Graphs, Structures, and Algorithms , vol- ume 28 of Algorithms and combinatorics. Springer, 2012

    2012

  4. [11]

    Sparsity

    Marcin Pilipczuk, Michał Pilipczuk, and Sebastian Siebertz. Lecture notes for the course “Sparsity” given at Faculty of Mathematics, Informatics, and Mechanics of the University of Warsaw, Winter semesters 2017/18 and 2019/20. Available online at https://www.mimuw.edu.pl/ mp24...

    2017

  5. [12]

    On the number of types in sparse graphs

    Michał Pilipczuk, Sebastian Siebertz, and Szymon Toru ´nczyk. On the number of types in sparse graphs. In 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2018 , pages 799–

    2018

  6. [13]

    Graph classes through the lens of logic

    Michał Pilipczuk. Graph classes through the lens of logic. ArXiv preprint, abs/2501.04166, 2025

    2025 arXiv

  7. [14]

    On the generalized coloring numbers

    Sebastian Siebertz. On the generalized coloring numbers. ArXiv preprint, abs/2501.08698, 2025

    2025 arXiv

  8. [16]

    Colouring graphs with bounded generalized colouring number

    Xuding Zhu. Colouring graphs with bounded generalized colouring number. Discrete Mathematics, 309(18):5562–5568, 2009. 12

    2009

Pith tools

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