{"id":"b1d59a79-9003-4892-a3d4-f34b27500168","arxiv_id":"2411.13656","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Every k-tangle in a graph is the lift of a k-tangle in a topological minor of size bounded by a function of k, reducing the vertex-set induction problem to bounded-size graphs.","lead":"Graph theorists ask whether every k-tangle, a formal notion of a cluster, is induced by a set of vertices voting by majority. This paper reduces that question to a finite check on graphs whose size is bounded by a function of k, and proves a bounded-weight version in full generality.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The claimed O(3^k k^5) bound in Theorems 1 and 5 is not derived and is inconsistent with the bounds actually supplied by Lemmas 5.5 and 5.6; the reduction's existence part may survive, but the theorem statements overclaim.","rationale":"The reader's designated weakest assumption is the unproved regularization Lemma 5.6 imported from [15]. I regard that as a legitimate but secondary concern: it is a cited published lemma, and the main residual risk there is whether the adaptation that drops one of its hypotheses is valid. The more concrete and checkable problem is the explicit O(3^k k^5) bound, which the reader also mentions in the rationale but does not make the primary weak point. The paper's own bounds in Lemmas 5.5 and 5.6, when composed with M=18k, produce a function vastly larger than O(3^k k^5); the sentence 'one may calculate' is not a derivation. Correcting this does not destroy the main reduction, because only finiteness of M(k) is needed for the qualitative reduction of Problem 1.1 to bounded-size graphs. It does require changing the statement of Theorem 1 and the corollaries that advertise the explicit bound, which is exactly the kind of correction the CONDITIONAL verdict should demand. I therefore keep the verdict unchanged and agree only partially with the reader's choice of weakest assumption.","tokens_in":42159,"tokens_out":12935,"duration_ms":1016660,"concrete_test":"Recompute M(k) symbolically from the paper's stated bounds: take ell=k, M=18k, let M1 = M1(ell,M) be the bound from the remark after Lemma 5.6, and let N1(k,M1) be the bound from Lemma 5.5. Compare N1(k,M1) with C*3^k*k^5 for k=4,5,6 and for asymptotically growing k. If the ratio N1/(3^k k^5) grows faster than polynomially, the O(3^k k^5) claim fails and Theorem 1, Corollary 2, and Corollary 8.4 must be restated with the actual bound or with no explicit bound.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central reduction only needs some finite M(k), but the paper's headline theorems and corollaries are stated with the explicit bound O(3^k k^5). That bound is never derived; the only support is the remark at the end of Section 7 that 'one may calculate' M(k) in O(3^k k^5). The calculation is not routine and is contradicted by the paper's own ingredients. Theorem 5 sets M(k)=N(k,18k), where N(k,M) is the bound in Theorem 5.1. Theorem 5.1 is proved by applying Lemma 5.5 with M1(k,M+2), and Lemma 5.5 already forces N1 to grow exponentially in a quantity like (M+2)^{k+1} (or worse, depending on how the ternary-tree path bound is read). Lemma 5.6 then inserts an additional M1(ell,M) with factorial dependence on ell, where ell can be as large as k. Substituting M=18k yields M(k) at least exp(Omega(k log k)), and in fact far worse, not O(3^k k^5). Thus the theorems as stated overclaim. The existence part of the reduction may survive after replacing the bound with the actual one, and the applications in Corollaries 2 and 3 remain valid qualitatively, but the advertised explicit bound and the computational corollary built on it need correction.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper claims a structural reduction for k-tangles: every k-tangle in a graph G survives as a k-tangle in a connected topological minor of G whose size is bounded by a function of k, and this reduction is presented as an inductive method for transferring weight functions and vertex sets that induce tangles. The main advertised result is an M(k) in O(3^k k^5) such that every k-tangle is induced by a weight function on a bounded-size topological minor, with corollaries reducing Problem 1.1 to finite verification and bounding the size of an inducing set when Problem 1.1 has a positive answer. The proof splits into a high-order-tangle case (Section 4) and a rainbow-cloud-decomposition case (Sections 5–7), after establishing special cases for low order, disconnected graphs, leaves, and degree-2 vertices in Section 3.","tokens_in":42359,"tokens_out":10015,"duration_ms":98016,"significance":"If the qualitative existence part holds, this is a significant contribution: it reduces an open question about tangles induced by vertex sets to a finite check for each fixed k, and it provides an inductive framework that may be useful beyond the specific problem. The detailed treatment of the lift/survive framework and the explicit constants in Lemmas 5.5 and 5.6 are strengths. However, the advertised explicit bound O(3^k k^5) is not established by the arguments in the manuscript, and the proof of Theorem 5 contains a gap between the number of edges and the number of vertices. The qualitative consequences may survive after replacing the bound with the actual one derived from the paper's ingredients, but the theorem statements as written overclaim.","major_comments":[{"comment":"The claimed bound M(k) ∈ O(3^k k^5) in Theorems 1, 4, 5 and Corollary 2 is never derived and appears inconsistent with the paper's own displayed bounds. The proof of Theorem 5.1 defines N(k,M) := N1(k, M1(k, M+2)), where Lemma 5.5 supplies N1(k,M) = 9k(M+2)^{k+1} and Lemma 5.6 supplies M1(ℓ,M) with a factorial dependence on ℓ. Substituting M = 18k gives a bound whose logarithm is already polynomial in k of degree larger than 1, certainly not O(k log k + 5 log k). The remark at the end of Section 7 that 'one may calculate' M(k) ∈ O(3^k k^5) is not a proof and is contradicted by these ingredients. The theorem statements must be corrected by either deleting the explicit O-bound or replacing it with the bound actually implied by Lemmas 5.5 and 5.6.","section":"§5 and §7, Lemma 5.5, Lemma 5.6, Theorem 5.1, end of §7"},{"comment":"The proof of Theorem 5 chooses M(k) := N(k, 18k) and applies Theorem 5.1 to a connected graph with minimum degree at least 3 and at least M(k) edges. However, Theorem 5.1 requires the graph to have at least N(k, 18k) vertices, not edges. Minimum degree at least 3 does not imply v ≥ e: a dense graph can have e much larger than v. Thus the proof as written does not justify the application of Theorem 5.1. This gap is repairable, for instance by using the bounded-tree-width bound available when no (k+1)-tangle exists to derive v ≥ e / O_k(1), but that factor is absent from the argument.","section":"§7, Proof of Theorem 5"},{"comment":"The proof of Theorem 5.1 relies entirely on Lemma 5.6, quoted from [15, Lemma 3.5], to obtain a linear decomposition with a foundational linkage satisfying (FL1) and (FL2). This is a load-bearing step for the entire rainbow-cloud-decomposition theorem, and hence for the second half of Theorem 5, but the paper does not state the lemma in full or prove it. The paper's definition of 'linear decomposition' includes conditions (L3) and (L4), and the cited lemma is from a paper co-authored by the present last author, so the exact match of hypotheses should be verified explicitly. At minimum, the paper should include the precise statement of Lemma 5.6 and a proof or a detailed verification that the hypotheses of [15, Lemma 3.5] are satisfied.","section":"§5, Proof of Theorem 5.1"}],"minor_comments":[{"comment":"The displayed formula for M1(ℓ, M) is garbled and hard to read; it should be typeset with explicit binomial coefficients and factorials so that the claimed bound can be checked.","section":"§5, remark after Lemma 5.6"},{"comment":"The notation T is used both for the set of all strictly increasing sequences and for a chosen element of that set; this makes the maximality argument harder to follow. Please use a different symbol for the set.","section":"§5, proof of Lemma 5.5"},{"comment":"The sentence 'We remark that one may calculate that M(k) ∈ O(3^k k^5)' should either be removed or replaced with a concrete derivation from the displayed N1 and M1 bounds, since this is not a routine verification in view of the bounds in Lemmas 5.5 and 5.6.","section":"§7, end of Section 7"}],"recommendation":"major_revision","confidential_remarks":"The qualitative reduction is potentially valuable, but the advertised O(3^k k^5) bound is not supported and the proof of Theorem 5 has an edges-versus-vertices gap. The reliance on Lemma 5.6 from [15] should be checked carefully, especially because it is from a co-authored paper; if the lemma is sound and the hypotheses match, a precise statement in the text will suffice. The existence parts may be repairable with a larger bound, so reject is not appropriate, but the current statements overclaim."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Main take: this paper gives a real reduction of Diestel–Hundertmark–Lemanczyk's question to finite graphs for each fixed k, and the inductive method behind it is genuinely useful. The advertised bound O(3^k k^5) is not derived and appears wrong; the existence result likely survives, but the theorem statements need correction.\n\nWhat is new and good: Theorem 4 (shrink a k-tangle to a bounded-size topological minor by edge deletion, vertex suppression, components) is a clean inductive framework. The lifting lemmas in Section 8 are careful and correctly handle suppression. Theorem 1 and Corollary 3 are the payoff: bounded total weight and reduction to finite check. The rainbow-cloud decomposition is a substantial new structural tool, and Section 6 develops its interaction with separations carefully. The proof does not assume the target result; no circularity.\n\nSoft spots: the claimed M(k) ∈ O(3^k k^5) is asserted with 'one may calculate' at the end of Section 7, but the ingredients contradict it. Lemma 5.5 gives N1(k,M) = 9k(M+2)^{k+1}, and Lemma 5.6 (from [15]) has a factorial factor; plugging M=18k yields M(k) at least exp(Omega(k log k)), far worse than the claimed bound. This affects Theorems 1, 4, 5, and Corollaries 2 and 8.4 as stated. The qualitative existence of some finite bound is not affected, and Corollary 3 (bounded total weight) only needs finiteness, so the main conceptual advance stands. A second concern, minor, is the use of Lemma 5.6 without proof; it is a published lemma from a paper co-authored by Wollan, so not circular, but a reader must chase the reference to verify it applies.\n\nWho this is for: people working on tangles, graph minors, and structural graph theory. It deserves a serious referee. My recommendation: engage with it, and require the authors to derive the correct bound (or restate results with a computable but unspecified bound), and to state Lemma 5.6 explicitly with the exact conditions used.","headline":"Strong reduction of the vertex-set tangle problem to finite graphs, but the advertised O(3^k k^5) bound is not derived and looks false; the existence result likely survives, so the paper deserves a serious referee with mandatory bound corrections.","tokens_in":42976,"tokens_out":2349,"would_cite":true,"duration_ms":24503,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C40","05C83","05C69"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that every k-tangle is the lift of a k-tangle in a connected topological minor with fewer than M(k) edges, with M(k) in O(3^k k^5), and uses this reduction to turn the vertex-set realization problem for tangles into a…","keywords":["tangles","tangles induced by vertex sets","rainbow-cloud decomposition","topological minors","weight functions","graph separations","tangle-tree duality"],"falsifier":"Exhibit, for some fixed $k$, an infinite family of connected graphs with minimum degree at least 3, no $(k+1)$-tangle, and arbitrarily many edges, such that every RC-decomposition has length bounded independently of the graph size; Theorem 5.1 explicitly rules this out. A more local test is to produce a linear decomposition satisfying the hypotheses of Lemma 5.5 for which no regularized decomposition with a foundational linkage meeting (FL1) and (FL2) of the required length exists, which would locate the failure in the borrowed regularity lemma.","tokens_in":41880,"feed_emoji":"🧩","tokens_out":13441,"duration_ms":127239,"temperature":0.7,"pith_summary":"The paper establishes a finite reduction for a structural question about tangles, the abstract 'clusters' of graph minor theory. It shows that every $k$-tangle in any graph comes from a $k$-tangle in a connected topological minor with fewer than $M(k)$ edges, where $M(k)\\in O(3^k k^5)$, and that realizing the small tangle by a weighted vertex set automatically realizes the original tangle by extending the weights by zero. This reduces the open question of whether every tangle is induced by the majority vote of a vertex set to a check over finitely many bounded-size graphs, and it proves that whenever that question has a positive answer for some $k$, every $k$-tangle is induced by a set of at most $M(k)$ vertices. It also shows unconditionally that every $k$-tangle is induced by a weight function whose total weight is bounded in $k$.","feed_headline":"All graph tangles live on bounded-size graph minors","feed_subtitle":"If every k-tangle is a majority vote on small graphs, the same holds on all graphs, so the open problem becomes a finite check.","key_machinery":"The load-bearing device is the rainbow-cloud decomposition (RC-decomposition), which packages a graph as a long 'rainbow' $R$ with a linear decomposition of constant adhesion $\\ell$ and a foundational linkage of $\\ell$ disjoint paths realizing every consecutive overlap, together with a 'cloud' $C$ meeting $R$ only at two end adhesion sets and a 'sun' $Z\\subseteq V(C)$ adjacent to every rainbow bag. Its role is to make the deletion of one edge controllable: with no $(k+1)$-tangle present and the graph large, tangle-tree duality yields a long linear decomposition, and a regularization lemma from [15] turns it into an RC-decomposition of length at least $18k$; deleting an edge deep in the rainbow produces new low-order separations whose orientations are either forced by the original tangle or decided by which side of the separation meets the cloud. The companion notion is 'survives': a tangle in $G$ survives as a tangle in $G'$ when it extends to it after an edge deletion or induces it after a vertex suppression or a passage to a component, reversing the usual lifting of tangles and letting the proof shrink the graph step by step.","core_discovery":"The central claim is a reduction with an explicit size bound: for every integer $k$ there is $M(k)\\in O(3^k k^5)$ such that every $k$-tangle $\\tau$ in a graph $G$ is the lift of some $k$-tangle $\\tau'$ in a connected topological minor $G'$ of $G$ with fewer than $M(k)$ edges, and any weight function inducing $\\tau'$ extends by zero to a weight function inducing $\\tau$. The route is an inductive shrinking procedure: a tangle 'survives' along a sequence in which the graph is reduced by deleting an edge, suppressing a degree-2 vertex, or passing to a proper component, until a connected graph of bounded size is reached. The hard case is a connected graph of minimum degree at least 3 with no $(k+1)$-tangle; there the proof builds a rainbow-cloud decomposition from a long linear decomposition and deletes an edge deep inside the rainbow. From the reduction the paper derives that the open majority-vote question for $k$-tangles only needs to be checked on connected graphs of bounded size, that a positive answer for fixed $k$ would give inducing vertex sets of size at most $M(k)$, and unconditionally that every $k$-tangle is induced by a weight function of total weight bounded in $k$.","pith_inferences":["One can try to settle the case $k=4$ by combining the $M(4)$ bound with the structural description of 4-tangles mentioned in the introduction: the finite list of bounded graphs could be checked against that description without brute-force enumeration.","A direct proof of the regularization lemma [15] used in Section 5, or a version specialized to tangles, would likely remove the current dependence on an external result and could substantially improve the bound $O(3^k k^5)$.","The reduction method is specifically graph-theoretic: vertex suppression and components have no direct analogues in matroids or abstract separation systems, where the weighted version already fails, so the bounded reduction should not be expected to transfer to those settings.","The same 'survives' induction could be applied to other tangle problems, such as bounding the size of a set of separations distinguishing two tangles, whenever the relevant property is stable under the three reduction steps."],"forward_implications":["The majority-vote question for a fixed $k$ becomes decidable in principle: it suffices to check all $k$-tangles in all connected graphs with fewer than $M(k)$ edges (Corollary 2).","If the majority-vote question has a positive answer for some fixed $k$, then every $k$-tangle is induced by a vertex set of size at most $M(k)$, not merely by some set of unbounded size (Corollary 3).","Every $k$-tangle is induced by some weight function whose total weight is bounded in $k$, so the support of the inducing weights can be chosen bounded (Corollary 3).","The surviving-tangle reduction gives a new bound $O(3^k k^5)$ on the size of a subgraph witnessing a $k$-tangle (Corollary 8.4).","The inductive method transfers any tangle property preserved under edge deletion, vertex suppression, and passing to components from bounded connected topological minors to all graphs."],"supporting_citations":[{"why":"It poses Problem 1.1, the vertex-set realization question that the paper reduces to bounded-size graphs, and supplies the formal definitions of inducing sets and weight functions.","marker":"[7]"},{"why":"It proves that every tangle is induced by some weight function (Theorem 1.2 here), which the paper needs to produce bounded-total-weight inductions in Corollary 3.","marker":"[10]"},{"why":"It supplies the regularization lemma (Lemma 5.6) that turns a long linear decomposition into one with a foundational linkage satisfying (FL1) and (FL2); the paper invokes this lemma without proof to build the rainbow-cloud decomposition.","marker":"[15]"},{"why":"It is the standard reference for the tangle-tree duality theorem used to obtain a long linear decomposition when the graph has no $(k+1)$-tangle, along with the graph-theoretic background.","marker":"[3]"},{"why":"It introduces tangles and the duality framework on which the paper's definitions and the high-order-tangle case rest.","marker":"[17]"}],"fun_headline_variants":["Tangles reduce to bounded-size graph minors","Every k-tangle lifts from a tiny minor","Majority-vote question for tangles is finite","Tangle inducing sets: bound the graph, then check","All k-tangles come from bounded-size subgraphs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof assumes a cited regularity lemma ([15, Lemma 5.6]) that any sufficiently long linear decomposition with a foundational linkage can be replaced by one whose linkage paths behave identically from bag to bag; the paper does not prove this lemma, and if it fails the rainbow-cloud decomposition—and with it the whole reduction to bounded-size graphs—may not exist.","fun_headline_variants_meta":{"raw":{"variants":["Tangles reduce to bounded-size graph minors","Every k-tangle lifts from a tiny minor","Majority-vote question for tangles is finite","Tangle inducing sets: bound the graph, then check","All k-tangles come from bounded-size subgraphs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00019,"raw_usage":{"total_tokens":1356,"prompt_tokens":982,"completion_tokens":374,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":598,"completion_tokens_details":{"reasoning_tokens":300}},"tokens_in":598,"tokens_out":374,"duration_ms":4461,"temperature":1.0,"reasoning_tokens":300,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T16:01:00.033910+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Exhibit, for some fixed $k$, an infinite family of connected graphs with minimum degree at least 3, no $(k+1)$-tangle, and arbitrarily many edges, such that every RC-decomposition has length bounded independently of the graph size; Theorem 5.1 explicitly rules this out. A more local test is to produce a linear decomposition satisfying the hypotheses of Lemma 5.5 for which no regularized decomposition with a foundational linkage meeting (FL1) and (FL2) of the required length exists, which would locate the failure in the borrowed regularity lemma.","supporting_citations":[{"cited_title":"K_6 minors in 6-connected graphs of bounded tree-width","cited_arxiv_id":"1203.2171","evidence_quote":"It supplies the regularization lemma (Lemma 5.6) that turns a long linear decomposition into one with a foundational linkage satisfying (FL1) and (FL2); the paper invokes this lemma without proof to build the rainbow-cloud decomposition."},{"cited_title":"La Sapienza","cited_arxiv_id":null,"evidence_quote":"It introduces tangles and the duality framework on which the paper's definitions and the high-order-tangle case rest."}],"review_version":1}