{"id":"b8926965-1015-4215-a74e-b6074da16893","arxiv_id":"2505.09834","paper_version":2,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Every graph of cliquewidth k admits a dominated partition whose quotient has treewidth k-1, yielding a 3-quasi-isometry and Assouad-Nagata dimension 1.","lead":"This paper improves the bridge between two graph width parameters, cliquewidth and treewidth, showing that every graph of cliquewidth k is 3-quasi-isometric to a graph of treewidth at most k-1. The proof is direct and structural, and it implies a sharp bound on a large-scale dimension parameter.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1 is proved only for the paper's customized cliquewidth-k pairs; the asserted equivalence to standard clique-width is never demonstrated.","rationale":"The reader's weakest-assumption diagnosis is correct and is the most load-bearing issue because it targets Theorem 1, the paper's main contribution. If the customized cliquewidth-k pairs define a strictly smaller class than standard cliquewidth, then the improved 3-quasi-isometry bound is not proved for all graphs of cliquewidth k. The paper explicitly concedes 'slight technical differences' in Section 2 but supplies no equivalence lemma; the remark that the OP2 target-used condition could be removed by colour permutations does not settle the nonempty-component and proper-subgraph restrictions. I also verified the secondary Lemma 12 arithmetic issue: 2c(c+1)/c - c equals c+2, not 2c+1, so the disjointness argument in Lemma 12 fails for c >= 2 and Theorem 2 is not proven as stated. Both issues are real, but the definitional gap is more central, so the conditional verdict is appropriate. The author should add a proof of equivalence with standard cliquewidth and repair or restate the tightness theorem.","tokens_in":14749,"tokens_out":22246,"duration_ms":244246,"concrete_test":"Give an induction on standard k-label clique-width expressions converting each operation into a sequence using only (OP1)-(OP3), explicitly handling relabellings i to j where j is unused; if the conversion fails, exhibit a graph whose minimum k under the customized definition exceeds its standard clique-width. A brute-force comparison of both definitions on all graphs with at most 7 vertices can quickly reveal such a counterexample if one exists.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The most load-bearing gap is in Section 2. The paper defines cliquewidth-k pairs with restrictions not present in the standard definition: (OP1) requires both components nonempty, (OP2) requires the target colour j already used, and (OP3) requires a proper subgraph, so edge insertions that add no new edges are forbidden. It notes 'slight technical differences' but never proves that the class of graphs admitting such pairs equals the class of graphs of standard clique-width at most k. Lemma 6 is proved entirely by induction over these customized operations, so it yields a dominated partition only for customized pairs. If the customized class is strictly smaller, then Theorem 3 and hence Theorem 1 are not established for standard clique-width-k graphs. The remark that the OP2 restriction can be removed by colour permutations does not address OP1/OP3, and no translation of arbitrary standard expressions is supplied. This is an omitted support for the main claim, not a disagreement with consensus.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies quasi-isometric comparison between graphs of bounded cliquewidth and graphs of bounded treewidth. It introduces a customized notion of cliquewidth-k pairs and proves (Lemma 6) that every such pair admits a c-monochromatic dominated partition whose quotient has treewidth at most k-1. This yields Theorem 3, and Lemma 7 converts any dominated partition into a 3-quasi-isometry, giving Theorem 1: every graph of cliquewidth at most k is 3-quasi-isometric to a graph of treewidth at most k-1. Theorem 2 gives a lower bound: for every c≥1 and k≥6, a sufficiently subdivided K_{k-2} has cliquewidth at most k and is not c-quasi-isometric to any graph of treewidth less than k-3. Section 6 applies Theorem 1 to show that graphs of cliquewidth at most k≥3 have Assouad-Nagata dimension 1.","tokens_in":14848,"tokens_out":13554,"duration_ms":134330,"significance":"If the two gaps identified below are closed, the paper gives a clear improvement over the previous (4k+4)-quasi-isometry to treewidth 6k, replacing it with a 3-quasi-isometry to treewidth k-1, together with a near-tight lower bound. The proof of Lemma 6 is well organized and genuinely inductive, and it is a strength that the main construction is direct and uses only the definitions of cliquewidth and treewidth. The application to Assouad-Nagata dimension via Lemmas 4 and 14 is natural and correctly observed. The paper is self-contained apart from the cited Lemma 4, and the comparison with the prior work of Hickingbotham and Nguyen-Scott-Seymour is clearly stated.","major_comments":[{"comment":"The paper defines cliquewidth using pairs (G,c) with additional restrictions: in (OP1) both components must be nonempty, in (OP2) the target colour j must already be used, and in (OP3) the subgraph G' must be proper. The text only says that there are 'slight technical differences' from other definitions and never proves that the class of graphs admitting such pairs equals the class of graphs of standard clique-width at most k. This is load-bearing because Lemma 6 and hence Theorem 3 are proved by induction on these customized operations, while Theorems 1 and 3 are stated for standard clique-width. The remark that the OP2 restriction can be removed by colour permutations does not address OP1 or OP3, and no translation of an arbitrary clique-width expression into a sequence of customized operations is supplied. Please add a normalization lemma, or prove directly that every standard clique-width-k graph admits such a pair.","section":"Section 2, definition of cliquewidth-k pairs"},{"comment":"In the proof, for distinct vertices v,v' of H, the paper derives dist_{G'}(f(X_v), f(X_v')) ≥ 2c(c+1)/c - c and states that this equals 2c+1. However 2c(c+1)/c - c = 2c+2 - c = c+2. Consequently dist_{G'}(X'_v, X'_v') ≥ c+2 - 2c = 2 - c, which is not at least 1 for c>2. The disjointness of the sets X'_v is essential for the minor argument, so Lemma 12 is not proved as written. The argument appears repairable, for instance by taking the neighbourhood radius r = c(c+3)/2 instead of c(c+1); the estimates then give a lower bound of 2c+1 before the final subtraction of 2c. But the current text needs a corrected proof.","section":"Section 5, Lemma 12"}],"minor_comments":[{"comment":"The sentence 'Since parts are nonempty, f is injective' is wrong; f is surjective when parts are nonempty, and the subsequent use of (QI2) relies on surjectivity.","section":"Section 4, Lemma 7"},{"comment":"In the case |V(P'_{i,j})| = 0, the text says the edge ij can be added 'using (OP2) (as i≠j)'; this should be (OP3), since (OP2) is a recolouring operation.","section":"Section 5, Lemma 11, Claim 1"},{"comment":"The sentence 'for each vv' in E(H) and each w in V(H) that is not an endpoint of ww'' uses the undefined symbol ww'; it should refer to vv' or to the edge under consideration.","section":"Section 5, Lemma 12"},{"comment":"The definition of an edge subdivided 'at least n times' is phrased as 'a path of length at least n+1', while a '≥n-subdivision' is defined as subdividing each edge 'at least n+1 times'; these two phrasings are inconsistent and should be aligned.","section":"Section 2, subdivision definitions"},{"comment":"The notation P_i and P_j is overloaded: it denotes both the set of old parts of a given colour and the union of the vertices of those parts; this makes the definition of the new partition P hard to parse and should be clarified.","section":"Section 3, OP3 case of Lemma 6"}],"recommendation":"major_revision","confidential_remarks":"The paper is appropriate for math.CO and the main results are likely correct once the equivalence between the customized and standard clique-width definitions is proved and Lemma 12 is corrected. I do not see a citation or novelty concern; the relation to the prior quasi-isometry results is clearly described."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper does what it says: it improves the known quasi-isometry relation between bounded cliquewidth and bounded treewidth. The main result, Theorem 3, gives a dominated partition whose quotient has treewidth k−1 for every graph of cliquewidth k, and the induced 3-quasi-isometry is a clean improvement over the previous (4k+4)-quasi-isometry to treewidth 6k. The proof of Lemma 6 is careful, and the three inductive cases (OP1–OP3) all check out. This is a genuine advance, not a repackaging.\n\nTwo soft spots, in proportion. First, the paper defines its own version of cliquewidth-k pairs, with restrictions that standard definitions do not have: nonempty components in (OP1), no 'useless' joins in (OP3), and a requirement that the target colour be used in (OP2). The author calls these 'slight technical differences' but never proves that the resulting class of graphs is exactly the standard cliquewidth-k class. To an expert the restrictions look harmless—you can purge empty unions, duplicate joins, and relabels to unused colours from any expression—but that normalization argument is absent. As written, Theorem 3 is literally about the custom pairs, and the bridge to the standard notion is asserted, not demonstrated. This is an omitted proof, not a fatal flaw.\n\nSecond, Lemma 12 contains a concrete arithmetic error. The paper claims 2c(c+1)/c − c = 2c+1; the left side is actually c+2. For c=1 the values agree, but for c>1 the claimed lower bound on distances in the target graph is too strong. The proof uses that bound to separate the sets X'_v and build the K_n-minor model. With the corrected value, the separation argument fails. So Theorem 2, the tightness result, is not proven as stated. It is probably repairable by subdividing the edges more (the required length should grow roughly like c^2, not c(c+1)), but as written it is a genuine gap in a secondary claim. The main theorem does not depend on this lemma.\n\nThe ANdim application in Section 6 is clean and follows from known results; the citations are appropriate. The paper is aimed at structural graph theorists who care about coarse geometry of dense graphs. I would send it to a serious referee: the main result deserves scrutiny and likely publication after the definitional equivalence is supplied and the arithmetic in Lemma 12 is either fixed or the tightness claim is softened.\n\nFor peer review: yes, engage with it, but condition acceptance on dealing with these two issues.","headline":"A genuinely better quasi-isometry theorem with two fixable gaps: an unproved equivalence in the custom clique-width definition and an arithmetic error in the tightness proof.","tokens_in":15479,"tokens_out":3469,"would_cite":true,"duration_ms":36138,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C75","05C83","05C12"],"pacs":[],"model":"deepseek-v4-flash","headline":"Every graph of cliquewidth at most $k$ is 3-quasi-isometric to a graph of treewidth at most $k-1$.","keywords":["cliquewidth","treewidth","quasi-isometry","dominated partition","tree decomposition","Assouad-Nagata dimension","graph subdivision","minor"],"falsifier":"Exhibit a graph of standard cliquewidth at most $k$ that cannot be built under the paper's restricted operations—for example, a cliquewidth expression that necessarily uses an empty component, recolours to an unused colour, or adds a complete bipartite edge set without a proper-subgraph step. If such a graph exists, then Theorem 3 is not proved for all standard cliquewidth-$k$ graphs.","tokens_in":14458,"feed_emoji":"🌲","tokens_out":5269,"duration_ms":52433,"temperature":0.7,"pith_summary":"This paper proves that every graph of cliquewidth at most $k$ can be partitioned into dominated pieces—each piece lying inside the closed neighbourhood of one vertex—so that the quotient graph has treewidth at most $k-1$. Because each such piece has weak diameter at most 2, the quotient map is a 3-quasi-isometry from the original graph to a graph of treewidth at most $k-1$, with a constant independent of $k$. This improves a previously known quasi-isometry with parameter $4k+4$ and treewidth $6k$, and it gives a direct construction driven by the cliquewidth operations themselves. The paper also shows that the treewidth bound is tight up to an additive constant, and derives that every class of graphs of cliquewidth at most $k$ has Assouad–Nagata dimension 1.","feed_headline":"Cliquewidth k graphs are 3-quasi-isometric to treewidth k-1","feed_subtitle":"Dense cliquewidth-k graphs have a dominated partition whose quotient is treewidth k-1, giving constant distortion.","key_machinery":"The key machinery is a dominated partition together with a tree decomposition of the quotient that is built in lockstep with the cliquewidth operations. More precisely, the induction maintains a $c$-monochromatic dominated partition $P$ and a tree decomposition of $G/P$ of width at most $k-1$, with two invariants: one distinguished bag that is rainbow under the induced colouring, and, for each used colour, the set of bags containing that colour forms a nonempty connected subtree. These invariants let the construction merge parts and add edges without losing the tree-decomposition bound, and the domination condition guarantees that every part has weak diameter at most 2, which is exactly what converts the partition into a 3-quasi-isometry.","core_discovery":"The central claim is Theorem 3: for every integer $k \\ge 1$, every graph $G$ of cliquewidth at most $k$ admits a dominated partition $P$ such that the quotient $G/P$ has treewidth at most $k-1$. A dominated partition is one where each part is contained in $N_G[v]$ for some vertex $v$, so each part is a locally small cluster; the quotient then inherits a tree-like structure. The paper proves this by induction on the operations that build a cliquewidth-$k$ pair, simultaneously constructing a tree decomposition of the quotient whose bags are small and whose colour subtrees are connected. Theorem 3 directly implies Theorem 1 via the observation that a dominated partition has parts of weak diameter at most 2 and hence induces a 3-quasi-isometry to the quotient.","pith_inferences":["If the same dominated-partition construction were implemented algorithmically, it would yield an explicit low-distortion embedding from any cliquewidth-$k$ graph into a treewidth-$(k-1)$ graph, which might be useful for turning treewidth-based algorithms into algorithms for dense cliquewidth-bounded graphs.","The connected colour-subtree invariants suggest that the quotient's tree decomposition can be lifted to a hierarchy of the original graph, not just of its quotient; this could imply stronger coarse geometric properties such as a constant bound on certain isoperimetric or separation profiles.","The tightness construction uses sufficiently subdivided complete graphs, hinting that the additive slack in the treewidth bound is an unavoidable cost of the domination requirement; testing whether subdivided complete graphs also obstruct smaller quasi-isometry constants would sharpen the constant in Theorem 1.","A natural testable extension is whether a similar dominated-partition argument works for linear cliquewidth, which would give a 3-quasi-isometry to a graph of bounded pathwidth rather than bounded treewidth."],"forward_implications":["Every graph of cliquewidth at most $k$ is 3-quasi-isometric to a graph of treewidth at most $k-1$; unlike the previous bound, neither the quasi-isometry constant nor the treewidth depends multiplicatively on $k$.","The domination property of the partition means the quasi-isometry is witnessed by a locally checkable object: each vertex's entire part lies within distance 2 of some chosen centre.","For every real $c \\ge 1$ and integer $k \\ge 6$, some graph of cliquewidth at most $k$ is not $c$-quasi-isometric to any graph of treewidth less than $k-3$, so the treewidth bound is tight up to an additive constant.","The class of all graphs of cliquewidth at most $k$ has Assouad–Nagata dimension 1 for every $k \\ge 3$, and dimension 0 for $k \\le 2$."],"supporting_citations":[{"why":"Supplies the classical comparison between cliquewidth and treewidth, including the bound that sparse graphs of bounded cliquewidth have bounded treewidth; this frames the problem and motivates the dense analogue.","marker":"[3]"},{"why":"Provides the prior result that graphs of bounded cliquewidth are quasi-isometric to graphs of bounded treewidth, and contains the observation that partitions with small weak diameter yield quasi-isometries; this is the baseline the paper improves.","marker":"[6]"},{"why":"Together with [6], gives the previous quasi-isometry with parameter $4k+4$ and treewidth $6k$; the paper's Theorem 1 improves both parameters.","marker":"[9]"},{"why":"Contains the lemma that sim-width is at most cliquewidth, which is part of the chain used to derive the earlier quasi-isometry bound.","marker":"[7]"},{"why":"Provides the comparison between cliquewidth and sim-width, another link in the earlier quasi-isometry derivation.","marker":"[10]"},{"why":"Proves that graphs of treewidth at most $k$ have Assouad–Nagata dimension 1, which the paper combines with Theorem 1 to bound the Assouad–Nagata dimension of cliquewidth-bounded graphs.","marker":"[5]"},{"why":"Independently proves the same treewidth Assouad–Nagata dimension result, supporting the application in Theorem 5.","marker":"[8]"}],"fun_headline_variants":["Cliquewidth k to treewidth k-1: 3-quasi-isometry","Dominated partition yields treewidth k-1 for cliquewidth k","Constant distortion: cliquewidth k is 3-quasi-isometric to treewidth k-1","Cliquewidth k graphs have quotient treewidth k-1, distortion 3","Tighter quasi-isometry: cliquewidth k to treewidth k-1 with constant 3"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof is carried out for a customized version of cliquewidth whose operations require nonempty components in disjoint unions, recolouring only to an already-used colour, and adding edges only to a proper subgraph; the paper states that this differs slightly from the standard definition but does not prove that the two definitions recognize exactly the same class of graphs.","fun_headline_variants_meta":{"raw":{"variants":["Cliquewidth k to treewidth k-1: 3-quasi-isometry","Dominated partition yields treewidth k-1 for cliquewidth k","Constant distortion: cliquewidth k is 3-quasi-isometric to treewidth k-1","Cliquewidth k graphs have quotient treewidth k-1, distortion 3","Tighter quasi-isometry: cliquewidth k to treewidth k-1 with constant 3"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001157,"raw_usage":{"total_tokens":4765,"prompt_tokens":891,"completion_tokens":3874,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":507,"completion_tokens_details":{"reasoning_tokens":3756}},"tokens_in":507,"tokens_out":3874,"duration_ms":24511,"temperature":1.0,"reasoning_tokens":3756,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T21:24:54.352329+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Exhibit a graph of standard cliquewidth at most $k$ that cannot be built under the paper's restricted operations—for example, a cliquewidth expression that necessarily uses an empty component, recolours to an unused colour, or adds a complete bipartite edge set without a proper-subgraph step. If such a graph exists, then Theorem 3 is not proved for all standard cliquewidth-$k$ graphs.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Contains the lemma that sim-width is at most cliquewidth, which is part of the chain used to derive the earlier quasi-isometry bound."},{"cited_title":"Proper Minor-Closed Classes of Graphs have Assouad-Nagata Dimension 2","cited_arxiv_id":"2308.10377","evidence_quote":"Proves that graphs of treewidth at most $k$ have Assouad–Nagata dimension 1, which the paper combines with Theorem 1 to bound the Assouad–Nagata dimension of cliquewidth-bounded graphs."},{"cited_title":"Assouad-Nagata dimension of minor-closed metrics.Proc","cited_arxiv_id":null,"evidence_quote":"Independently proves the same treewidth Assouad–Nagata dimension result, supporting the application in Theorem 5."}],"review_version":1}