{"id":"e8f8f347-6189-41c3-a736-c359505145bc","arxiv_id":"2505.15655","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":8.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"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.","lead":"This paper proves that several natural hierarchies of sparse graphs, such as graphs of bounded treewidth, cannot be encoded into one another using first-order logic transductions. It introduces the growth rate of weak coloring numbers as a new invariant for proving such non-embeddability results.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified: the central reduction is sound; only external degree bounds are dependencies.","rationale":"I read the paper in good faith and checked the load-bearing steps. Theorem 3.1's proof uses Theorem 3.2 correctly: for each S = WReach_d[u] cap WReach_d[v], Claim 3.5 gives d-separation, so the color pair determines adjacency. The matching/Ramsey argument in Claim 3.6 is valid: in the clique case one obtains K_{t,t} in H, and in the independent set case Lemma 3.4 gives the contradiction s^s <= s*(s-1)^{s-1} < s^s. The model eta satisfies the edge-touching condition, connectedness/radius bounds, and congestion; the only blemish is the omitted direct term {u} in Claim 3.9, which is an additive constant and hence irrelevant to the existence of some k. Lemma 4.1's inequality wcol_d(H) <= k*wcol_{(4k+1)d}(G) is correct: each edge of a path in H can be lifted to a path of length at most 4k+1 in G, the lifted walk witnesses weak reachability from gamma(v), and congestion bounds the multiplicity by k. The domination of pi_C over pi_D follows with c = 4k+1. The applications then depend only on the known polynomial degrees for treewidth, Hadwiger, and planar classes. These estimates are published and standard; I found no internal reason to doubt them. The paper explicitly relies on them rather than re-deriving them, and the reader's weakest assumption correctly identifies that dependency, but it is a normal citation of established results, not a defect in the argument. The minor off-by-one in Claim 3.9 does not change the verdict. Therefore I recommend keeping the reader's ACCEPT verdict unchanged.","tokens_in":13981,"tokens_out":30803,"duration_ms":268825,"concrete_test":"Independently re-derive the cited weak-coloring degree estimates from [8,15]: verify pi_Tt(d) = binom(d+t,t), pi_Ht(d) between Omega(d^{t-1}) and O(d^t), and pi_planar(d) = O(d^3). If any exponent changes, the corresponding non-transducibility statement in Theorems 1.1-1.3 would need revision; otherwise the main claims stand.","verdict_should_be":"UNCHANGED","load_bearing_attack":"No significant objection identified. The central chain Theorem 3.1 -> Lemma 4.1 -> Corollary 4.2 is internally sound: the Local Feferman-Vaught step, the Bollobas-type counting in Lemma 3.4, the construction of the congested shallow minor model, and the weak-coloring pullback argument in Lemma 4.1 all check out. The only non-re-derived inputs are the published weak-coloring degree estimates [8,15] used in the proofs of Theorems 1.1-1.3; these are standard and, being asymptotic in degree, are not endangered by constant shifts. A tiny exposition gap exists in Claim 3.9: the direct term {u} in eta(u) is not counted through X_w, so the congestion bound should be s*f+1 rather than s*f; however, since the theorem only requires existence of some k, adding 1 to the constant repairs it without affecting any conclusion. Lemma 3.10's converse invokes [2, Cor. 7.6], but that converse is not used for the main separations.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":14057,"tokens_out":17073,"duration_ms":138582,"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.","major_comments":[],"minor_comments":[{"comment":"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.","section":"Claim 3.9"},{"comment":"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.","section":"Proof of Claim 3.6"},{"comment":"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.","section":"Lemma 3.4"},{"comment":"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.","section":"Lemma 4.1"},{"comment":"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.","section":"Proof of Theorem 3.1"},{"comment":"There is a typo in 'wcol(4k+1))d(G, ≼)' with an extra parenthesis; also 'letη' should be 'let η'.","section":"Section 4, around Eq. (4.1)"}],"recommendation":"minor_revision","confidential_remarks":"For the editor: This is a technically strong paper and the central reduction is sound. The minor errors listed above are local and do not affect any theorem. I recommend acceptance after minor revision. The non-transducibility corollaries inherit their conclusions from the published weak-coloring degree bounds in [8] and [15]; the authors do not re-derive these, but the bounds are standard and correctly cited, and only the polynomial degrees are needed for the separations."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The short version: this is a strong paper. It proves the strict treewidth hierarchy for FO transducibility (open since Braunfeld et al.), plus Hadwiger and planar separations, and the engine is a new invariant: the polynomial degree of weak coloring numbers. I checked the main line and it holds.\n\nWhat is actually new: Theorem 3.1, saying that if a weakly sparse class D is transducible from bounded-expansion C, then D is contained in k-congested depth-k minors of C° (C plus a universal vertex). That is a real structural characterization, not a repackaging of the pathwidth or 3D-grid results. Lemma 4.1 shows that adding a universal vertex and taking congested shallow minors preserve the degree of the weak d-coloring number as a polynomial in d. Combined with known bounds, this yields the three headline separations. The proof of Lemma 3.3 is detailed and internally consistent: the weak reachability intersection sets, the Ramsey-based partition, and the Bollobás counting all line up.\n\nCredit where due: the paper is honestly written, states its dependencies, and does not oversell its converse. The applications are clean corollaries of published weak coloring bounds, not re-derivations.\n\nSoft spots, in proportion: the main results inherit the lower/upper bounds on weak coloring numbers from [8,15]. If any of those were off, the corresponding corollary would fall. That is normal, but the paper does not re-derive them, so a referee should double-check those citations are used correctly. The only real issue I found is tiny: in Claim 3.9 the direct term {u} in η(u) is not counted through X_w, so the congestion bound should be s·f+1 rather than s·f. Since the theorem only needs existence of some k, adding 1 fixes it and nothing downstream changes. Also, the converse Lemma 3.10 invokes [2, Cor. 7.6] but that converse is not used for the separations, so a possible dependency there is harmless.\n\nWho it is for: anyone working on the transducibility quasi-order, sparse graph structure, or weak coloring numbers. It deserves a serious referee. I would send it out.\n\nRecommendation: accept after minor revision; the congestion constant typo should be corrected.","headline":"A clean proof that weak coloring number degree is a FO-transduction invariant, resolving the treewidth hierarchy question and giving sharp separations.","tokens_in":14710,"tokens_out":1763,"would_cite":true,"duration_ms":14745,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["03C13","05C83","68Q19"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["first-order transductions","bounded expansion","weak coloring numbers","treewidth","Hadwiger number","planar graphs","congested shallow minors","sparse graphs"],"falsifier":"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.","tokens_in":13714,"feed_emoji":"🔀","tokens_out":10455,"duration_ms":86187,"temperature":0.7,"pith_summary":"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.","feed_headline":"Treewidth t+1 resists all first-order transductions from treewidth t","feed_subtitle":"The proof: a transduction must preserve the degree of weak coloring numbers, and each treewidth step shifts that degree.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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"],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the Local Feferman–Vaught theorem (Theorem 3.2) in the color-palette formulation that powers the proof of Theorem 3.1.","marker":"[3]"},{"why":"Also supplies the Local Feferman–Vaught theorem / type-counting lemma used in the same step.","marker":"[12]"},{"why":"Provides the exact weak coloring number binom(d+t,t) for treewidth-t graphs, the Ω(d^{t−1}) lower bound for Hadwiger classes, and the Θ(d^4) lower bound for treewidth-4, all used in Theorems 1.1–1.3.","marker":"[8]"},{"why":"Provides the O(d^t) upper bound for Hadwiger classes and the O(d^3) upper bound for planar graphs, used to derive the negative transducibility results.","marker":"[15]"},{"why":"Characterizes bounded expansion by finiteness of all weak coloring numbers (Theorem 2.3), which is used to bound the parameter s in the proof of Theorem 3.1.","marker":"[16]"},{"why":"Supplies the converse direction (Claim 3.11) for the characterization of transducibility with copying among bounded-expansion classes, and motivates the treewidth hierarchy question resolved by Theorem 1.1.","marker":"[2]"}],"fun_headline_variants":["First-order transductions can't climb treewidth t to t+1","Treewidth t+1 not FO-transducible from treewidth t","No FO transduction can raise treewidth or Hadwiger number","Sparse graphs: FO logic can't increase weak coloring degree","Treewidth and Hadwiger steps resist first-order transductions"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["First-order transductions can't climb treewidth t to t+1","Treewidth t+1 not FO-transducible from treewidth t","No FO transduction can raise treewidth or Hadwiger number","Sparse graphs: FO logic can't increase weak coloring degree","Treewidth and Hadwiger steps resist first-order transductions"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000725,"raw_usage":{"total_tokens":3343,"prompt_tokens":1134,"completion_tokens":2209,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":750,"completion_tokens_details":{"reasoning_tokens":2118}},"tokens_in":750,"tokens_out":2209,"duration_ms":16434,"temperature":1.0,"reasoning_tokens":2118,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T15:13:41.578771+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Lacon-, shrub- and parity-decompositions: Characterizing transductions of bounded ex- pansion classes","cited_arxiv_id":null,"evidence_quote":"Supplies the Local Feferman–Vaught theorem (Theorem 3.2) in the color-palette formulation that powers the proof of Theorem 3.1."},{"cited_title":"On the number of types in sparse graphs","cited_arxiv_id":null,"evidence_quote":"Also supplies the Local Feferman–Vaught theorem / type-counting lemma used in the same step."},{"cited_title":"Stavropoulos","cited_arxiv_id":null,"evidence_quote":"Provides the exact weak coloring number binom(d+t,t) for treewidth-t graphs, the Ω(d^{t−1}) lower bound for Hadwiger classes, and the Θ(d^4) lower bound for treewidth-4, all used in Theorems 1.1–1.3."},{"cited_title":"On the generalised colouring numbers of graphs that exclude a fixed minor","cited_arxiv_id":null,"evidence_quote":"Provides the O(d^t) upper bound for Hadwiger classes and the O(d^3) upper bound for planar graphs, used to derive the negative transducibility results."},{"cited_title":"Colouring graphs with bounded generalized colouring number","cited_arxiv_id":null,"evidence_quote":"Characterizes bounded expansion by finiteness of all weak coloring numbers (Theorem 2.3), which is used to bound the parameter s in the proof of Theorem 3.1."}],"review_version":1}