{"id":"90b89986-c19b-40b1-968b-88da8f61b964","arxiv_id":"2607.16778","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":8.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"The treewidth of the strong product of two graphs is at least the product of their treewidth-plus-ones, minus one; analogous bounds hold for pathwidth and Cartesian products.","lead":"This paper proves a sharp lower bound on the treewidth of strong products of graphs, improving a previous result and solving an open problem of Hickingbotham and Wood. The same method yields bounds for pathwidth, Cartesian products, and strict brambles, and shows products of expanders contain large expander subgraphs.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No load-bearing objection to Theorem 1; proof is sound. Only unproved Fact 21 affects Theorem 8, so CONDITIONAL stands.","rationale":"The reader's weakest-assumption analysis identifies Fact 21 as the only unproved step, and correctly notes that it is load-bearing only for the secondary Theorem 8. My independent check of Theorem 1's proof found no hidden assumption: the bramble projection argument is valid, the size inequalities are correct, and the minor typo in the edge-touching case does not affect the mathematics. Since the central theorem is secure and the only gap is a missing proof of a plausibly true secondary lemma, the reader's CONDITIONAL verdict should remain unchanged. I agree with the reader's assessment rather than escalating to REJECT or relaxing to ACCEPT, because the unproved Fact 21 is still a real omission in the manuscript as written.","tokens_in":13276,"tokens_out":27093,"duration_ms":218582,"concrete_test":"Independently derive Fact 21 by adapting the standard proof of Fact 10 (Reed [16]) to lenient tree-decompositions: suppose a strict bramble S has no bag as a hitting set, and use the pairwise-intersection property plus the lenient-property to force a hitting set of size exceeding max_t |ℓ(t)|. If the derivation succeeds, Theorem 8 is fully supported; if it fails, Theorem 8 should be downgraded to a conjecture. Theorem 1 is unaffected in either case.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim, Theorem 1, is internally sound. The layered bramble construction B_v and the projected tree-decomposition β' are standard, and the inequalities check: β(t) hitting B_v gives |β(t)∩(V(G)×{v})| ≥ ord(B_v)=bn(G), and the vertex/edge properties of β' follow from Facts 9 and 10. The edge-property paragraph contains a wording typo ('If U∩V=∅ ... On the other hand, there exists w∈U∩V'), but the intended case distinction is clear and correct. The only substantive gap in the manuscript is Fact 21, asserted as 'similar to Facts 9 and 10' but not proved. Fact 21 is used solely in the proof of Theorem 8 (strict bramble number of Cartesian products); Theorem 1 depends only on the cited Facts 9 and 10. Thus the main claim is not endangered. A conditional acceptance while the missing proof of Fact 21 is supplied (or a citation given) is the appropriate disposition.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the treewidth and pathwidth of strong, Cartesian, and lexicographic products. Its main result (Theorem 1) is the lower bound tw(G ⊠ H) ≥ (tw(G)+1)(tw(H)+1)−1, improving on the previously known bound tw(G ⊠ H) ≥ (tw(G)+1)had(H)−1 of Kozawa–Otachi–Yamazaki and Hickingbotham–Wood, and solving the latter authors' open problem with constant c=1. The bound is optimal by the complete-graph example. The proof is a bramble-lifting argument: from a tree-decomposition of G ⊠ H and a maximum-order bramble in G, the author projects each bag to the set of H-vertices whose corresponding lifted bramble it hits, showing the projected bags form a tree-decomposition of H. The paper also proves the analogous pathwidth bound (Theorem 2) via stoppages, a Cartesian-product treewidth bound (Theorem 3) with best-possible constant 1/2, a strict-bramble product inequality (Theorem 8), a non-tightness result between lexicographic and strong products (Theorem 6), and an application to products of expanders (Theorem 16). The central derivations are internally sound; the main unresolved issue is that two facts used in the proof of Theorem 8 are stated without proof.","tokens_in":13519,"tokens_out":17704,"duration_ms":158343,"significance":"If the proofs are completed, this is a substantial contribution. Theorem 1 is a clean, parameter-free improvement over the previous Hadwiger-number bound; since Hadwiger number can be much smaller than treewidth (e.g., for grids), the improvement is real and not merely cosmetic. The bramble-lifting technique is elegant, and the pathwidth analogue via stoppages is nontrivial and appears correct as written. The application to expanders is a nice consequence. The proof of Theorem 8, however, depends on Fact 21 (and Fact 20), which the manuscript asserts without proof or citation. Fact 21 is not an immediate consequence of the cited duality theorem (Theorem 19) as stated, so this missing argument is a load-bearing gap for the strict-bramble product theorem. The main theorem, Theorem 1, does not rely on this gap.","major_comments":[{"comment":"Facts 20 and 21 are stated as 'basic facts' with proofs 'similar to Facts 9 and 10', but no proof or precise citation is given. Fact 21 is used essentially at the start of the proof of Theorem 8, where the author invokes it to obtain a node whose lenient bag hits each lifted strict bramble S_v. Fact 20 is used in the same proof to establish the vertex-property of (T, ℓ'). Theorem 19 as quoted only asserts equality between the minimum lenient width and sbn(G); it does not directly imply Fact 21. I have checked that both facts are true: for Fact 21, the sets T_A = {t : ℓ(t)∩A≠∅} are nonempty connected subtrees, and for a strict bramble they pairwise intersect, so by the Helly property for trees they have a common node. But the manuscript must supply this argument (or a reference), because as written Theorem 8 is not fully verified.","section":"Section 6, Facts 20–21"}],"minor_comments":[{"comment":"In the edge-property paragraph, after 'If U∩V = ∅' the next sentence reads 'On the other hand, there exists w∈U∩V', which is missing the case condition. It should read 'If U∩V ≠ ∅, choose w∈U∩V'.","section":"Section 2, proof of Theorem 1"},{"comment":"In the second direction of Lemma 13, the sentence 'Since Y⊆X, it follows that (V(G)\\X)∪∂X⊆(V(G)\\Y)∪∂Y' is not generally true. The subsequent conclusion G[X]∪G[Z]=G does follow directly from the definition of Z=(V(G)\\Y)∪∂Y and Y⊆X, so the proof is repairable, but the displayed implication should be corrected.","section":"Section 6, proof of Lemma 13"},{"comment":"The stoppages in G and H are denoted by the same symbols as the graphs themselves ('Let G be a stoppage ... and let H be a stoppage ...'), which is confusing in plain text. Use calligraphic letters, e.g., \\mathcal{G} and \\mathcal{H}.","section":"Section 3, proof of Theorem 2"},{"comment":"In the private-communication argument, the sentence 'Then (T,β′) is a tree-decompositionG □H' appears to have a typo: it should be 'a tree-decomposition of G ⊠H'.","section":"End of Section 6, Question 23 discussion"},{"comment":"From tw(S) ≥ c|V(G∗H)| and tw(S) ≤ |V(S)|−1 one obtains |V(S)| ≥ c|V(G∗H)|+1, not c|V(G∗H)|−1. The displayed inequality is true but weaker than what follows; the weaker bound is harmless.","section":"Section 4, proof of Theorem 16"},{"comment":"The sentence in the Question 23 argument should also clarify that the orientation of G is chosen with maximum out-degree degen(G), not just any orientation; this is implicit but could be stated explicitly.","section":"Section 6, final paragraph"}],"recommendation":"major_revision","confidential_remarks":"The main theorem is sound and the paper is close to acceptance. The only substantive gap is the missing proof of Fact 21 (and Fact 20) in Section 6, which is load-bearing for Theorem 8. The missing argument is short and standard, so I expect a revision to resolve the issue without changing the paper's scope. I would be happy to accept once the proof or a precise citation is supplied."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Main thing to know: the central theorem is real. Kaul proves tw(G⊠H) ≥ (tw(G)+1)(tw(H)+1)−1, which solves Hickingbotham and Wood's open problem with c=1, and it's optimal. The proof via bramble lifting is standard but clean, and I checked the key steps; the construction of the projected tree-decomposition of H works. The pathwidth analogue (Theorem 2) uses stoppages, which is heavier machinery but the argument appears complete. The Cartesian product bound, the strict bramble product bound, and the expander application are all plausible and fill out the paper nicely.\n\nSoft spots are modest. Fact 21 — that every strict bramble is hit by some bag of a lenient tree-decomposition — is asserted with 'similar to Facts 9 and 10' but not proved. That matters only for Theorem 8, so the main result doesn't depend on it, but Theorem 8 is a stated contribution, so the author should add a proof or a citation. There's also a genuine typo in the edge-property paragraph of Theorem 1's proof: the case split reads 'If U∩V=∅ ... On the other hand, there exists w∈U∩V.' The intended meaning is clear (if disjoint use an edge in G, otherwise use the common vertex), but it should be fixed. Minor. A few external facts — Theorem 14, Theorem 15, the sbn(G) ≥ (tw(G)+1)/2 bound — are cited rather than proved, which is fine.\n\nThe citation pattern looks honest: previous work by Kozawa–Otachi–Yamazaki and Hickingbotham–Wood is acknowledged, and the new inequalities are derived from established duality theorems rather than fitted to the target.\n\nWho's this for: anyone working in structural graph theory, especially on graph products and treewidth. The paper deserves a serious referee. I'd send it to peer review; the only required change is a proof (or precise citation) for Fact 21, plus fixing the typo. With that, it's publishable.","headline":"Sharp, clean solution to an open problem on treewidth of strong products, with a sound main proof and only minor gaps (an unproved lemma for a side theorem and a wording typo).","tokens_in":13994,"tokens_out":2123,"would_cite":true,"duration_ms":20674,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C83","05C75"],"pacs":[],"model":"deepseek-v4-flash","headline":"The treewidth of a strong product is at least the product of the factors' treewidths.","keywords":["treewidth","strong product","Cartesian product","bramble number","strict bramble number","pathwidth","vertex expansion","graph products"],"falsifier":"Compute treewidth of G⊠H for a pair of small graphs where both factors have treewidth at least 2; a value below (tw(G)+1)(tw(H)+1)−1 would refute the main theorem. For the strict result, find a strict bramble and a lenient tree-decomposition such that no bag intersects every bramble member; that would invalidate the auxiliary duality used in Theorem 8.","tokens_in":13167,"feed_emoji":"","tokens_out":6560,"duration_ms":58696,"temperature":0.7,"pith_summary":"The paper proves that for every pair of finite graphs, the treewidth of their strong product is at least (treewidth of G + 1)(treewidth of H + 1) − 1, which is exactly the value for complete graphs and therefore cannot be improved in general. This settles a recent open question, improving on earlier work that only gave a lower bound using a clique-minor parameter of one factor. The proof is built on a bramble projection: a maximum bramble in one factor is lifted into the product, and a tree-decomposition of the product is coerced into a tree-decomposition of the other factor. The same method yields a sharp pathwidth analogue, a best-possible (up to constant factor) bound for Cartesian products, and a multiplicative lower bound for strict brambles in Cartesian products. An application shows that products of graph classes with positive vertex expansion contain linearly large subgraphs that are themselves expanders.","feed_headline":"Strong product treewidth reaches the product of factor treewidths","feed_subtitle":"A bramble projection trick settles a recent open problem and is tight for complete graphs.","key_machinery":"The engine is the bramble number, a parameter equal to treewidth plus one: a bramble is a family of connected vertex sets that pairwise touch, and its order is the size of the smallest hitting set. The proof lifts a bramble from one factor into the strong product and uses the product's edges to show that lifted families over adjacent factor vertices touch, creating larger brambles. It then applies the standard duality that every bramble is hit by some bag of every tree-decomposition, forcing a projection of the decomposition onto the second factor. For pathwidth, the same projection is run with stoppages—symmetric families of cuts dual to pathwidth—and for strict brambles (pairwise intersect","core_discovery":"The central claim, Theorem 1, is that tw(G⊠H) ≥ (tw(G)+1)(tw(H)+1)−1 for all graphs G and H. The proof takes a maximum bramble in G, lifts every member A to A×{v} for each vertex v of H, and observes that the union of these lifted brambles over an edge of H is still a bramble in the strong product. A minimum-width tree-decomposition of the product is then projected: a vertex v of H is placed in a bag of the projected decomposition exactly when the corresponding bag of the product decomposition hits the lifted bramble at v. Standard bramble/tree-decomposition duality forces the projected bags to form a tree-decomposition of H, and size counting gives the inequality. The paper also proves the","pith_inferences":["The bramble-projection technique is general enough that it likely yields analogous lower bounds for other parameters that have a hitting-set dual, such as other width parameters defined by decompositions.","The pairing of strong product with bramble number and Cartesian product with strict bramble number suggests a design principle: sparser products need stricter hitting-set families; this could predict which parameter/product pairings are tractable for other products like lexicographic products.","For expander products, the proof gives existence of a large expander subgraph but no explicit construction; a computational search could reveal whether the constant can be improved for bounded-degree factors."],"forward_implications":["Solves the open problem of whether tw(G⊠H) ≥ c·tw(G)tw(H) with a positive constant: c=1 works.","The bound is tight because complete graphs K_m ⊠ K_n have treewidth mn−1.","The Cartesian bound tw(G□H) ≥ ½(tw(G)+1)(tw(H)+1)−1 is best possible up to the constant ½.","If G and H are graph classes with positive vertex expansion, then any product G□H, G⊠H, or G◦H contains a subgraph of size linear in the product that is an expander.","The strict bramble number of a Cartesian product is at least the product of the strict bramble numbers of the factors."],"fun_headline_variants":["Strong product treewidth hits factor product bound","Bramble projection solves strong product treewidth open problem","New treewidth lower bound for strong products is tight","Product graph treewidth bound proven via bramble lifting"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The strong-product lower bound assumes the classical bramble–treewidth duality theorem, while the strict-bramble product inequality additionally assumes an unproved companion duality for lenient tree-decompositions; if these dualities fail, the corresponding product bounds collapse.","fun_headline_variants_meta":{"raw":{"variants":["Strong product treewidth hits factor product bound","Bramble projection solves strong product treewidth open problem","New treewidth lower bound for strong products is tight","Product graph treewidth bound proven via bramble lifting"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00075,"raw_usage":{"total_tokens":3175,"prompt_tokens":741,"completion_tokens":2434,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":485,"completion_tokens_details":{"reasoning_tokens":2385}},"tokens_in":485,"tokens_out":2434,"duration_ms":17823,"temperature":1.0,"reasoning_tokens":2385,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-01T19:58:50.850502+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute treewidth of G⊠H for a pair of small graphs where both factors have treewidth at least 2; a value below (tw(G)+1)(tw(H)+1)−1 would refute the main theorem. For the strict result, find a strict bramble and a lenient tree-decomposition such that no bag intersects every bramble member; that would invalidate the auxiliary duality used in Theorem 8.","supporting_citations":[],"review_version":1}