REVIEW 3 major objections 3 minor 17 references
On vertex sets inducing tangles
T0 review · 3 major / 3 minor · reviewed 2026-08-12 · deepseek-v4-flash
Pith's one-line read 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…
desk verdict 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. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
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.
What would settle it
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.
Extended reading notes
Core claim
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$.
Load-bearing premise
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.
Editorial extensions
If this is right
- 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.
Reading between the lines
- 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.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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.
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 (3)
- [§5 and §7, Lemma 5.5, Lemma 5.6, Theorem 5.1, end of §7] 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.
- [§7, Proof of Theorem 5] 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.
- [§5, Proof of Theorem 5.1] 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.
minor comments (3)
- [§5, remark after Lemma 5.6] 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.
- [§5, proof of Lemma 5.5] 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.
- [§7, end of Section 7] 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.
Circularity Check
No circularity: the bounded-size reduction is derived from independent structural lemmas; the cited [15] lemma is not the target result.
full rationale
The paper's central claim is a reduction: every k-tangle in a graph G is the lift of a k-tangle in a topological minor whose size is bounded in k, and any weight function inducing the smaller tangle extends by zero to one inducing the original. The derivation is self-contained apart from two external ingredients: the tangle-tree duality theorem from [3] and Lemma 5.6 from [15]. Neither is equivalent to the target theorem. Lemma 5.6 is a regularization statement about linear decompositions with foundational linkages satisfying (FL1) and (FL2); it does not mention tangles induced by vertex sets, weight functions, or bounded topological minors. Although [15] has Wollan as a co-author, the lemma is a distinct published structural result with its own assumptions (long linear decomposition, adhesion, property (R1)) and does not presuppose the existence of the bounded-size reduction. The subsequent proof constructs RC-decompositions, analyzes rainbow-crossing and rainbow-slicing separations, and defines extensions locally; no parameter is fitted to data and then renamed as a prediction. The O(3^k k^5) bound asserted in Theorems 1, 4, and 5 is not actually derived and may be a correctness overclaim, but that is not circularity: the existence part of the argument does not reduce to that bound, and the bound is not an input that is later called a prediction. The only self-citation overlap is the invocation of Lemma 5.6 from [15], but because that lemma is independent support with a published proof and is not the central claim, it does not raise the circularity score.
Assumptions & free parameters
assumptions (4)
- standard math Tangle-tree duality: every graph without a (k+1)-tangle admits a tree-decomposition of adhesion at most k and width less than 3k whose induced separations are distinct and locally consistent.
- domain assumption Lemma 5.6 from [15]: a long linear decomposition of adhesion ell satisfying (R1) can be transformed into one of length at least M with a foundational linkage satisfying (FL1) and (FL2).
- domain assumption Elbracht-Kneip-Teegen Theorem 1.2: every tangle in a graph is induced by some weight function V(G) to N.
- standard math Standard graph theory: Menger's theorem, regularity, consistency and the profile property of tangles are used throughout.
Cite this review
Pith. "Pith review of On vertex sets inducing tangles." pith.science (2026). https://pith.science/paper/UOBZTYUR
@misc{pith2026241113656,
author = {Pith},
title = {Pith review of: On vertex sets inducing tangles},
year = {2026},
howpublished = {\url{https://pith.science/paper/UOBZTYUR}},
note = {Machine review of arXiv:2411.13656}
}
abstract
Diestel, Hundertmark and Lemanczyk asked whether every $k$-tangle in a graph is induced by a set of vertices by majority vote. We reduce their question to graphs whose size is bounded by a function in $k$. Additionally, we show that if for any fixed $k$ this problem has a positive answer, then every $k$-tangle is induced by a vertex set whose size is bounded in $k$. More generally, we prove for all $k$ that every $k$-tangle in a graph $G$ is induced by a weight function $V(G) \to \mathbb{N}$ whose total weight is bounded in $k$. As the key step of our proofs, we show that any given $k$-tangle in a graph $G$ is the lift of a $k$-tangle in some topological minor of $G$ whose size is bounded in $k$.
Reference graph
Works this paper leans on
-
[15]
K_6 minors in 6-connected graphs of bounded tree-width
K.-i. Kawarabayashi, S. Norine, R. Thomas, and P. Wollan,K6 minors in 6-connected graphs of bounded tree-width, Journal of Combinatorial Theory, Series B136 (2012), available at arXiv:1203.2171
work page Pith review arXiv 2012
-
[1]
G. Birkhoff,Lattice theory, revised edition, Colloquium publications, American Mathematical Society, 1948
work page 1948
-
[2]
Characterising 4-tangles through a connectivity property
J. Carmesin and J. Kurkofka,Characterising 4-tangles through a connectivity property, arXiv preprint (2023), available at arXiv:2309.00902
work page Pith review arXiv 2023
-
[3]
Diestel,Graph Theory, 5th ed., Springer, 2017
R. Diestel,Graph Theory, 5th ed., Springer, 2017
2017
-
[4]
, Abstract separation systems, Order 35 (2018), 157–170, available at arXiv:1406.3797
arXiv 2018
-
[5]
, Tree sets, Order 35 (2018), no. 1, 171–192, available at arXiv:1512.03781
work page Pith review arXiv 2018
-
[6]
R. Diestel, C. Elbracht, and R. W. Jacobs,Point sets and functions inducing tangles of set separations, Journal of Combinatorics 15 (2024), no. 3, 283–306, available at arXiv:2107.01087
arXiv 2024
-
[7]
R. Diestel, F. Hundertmark, and S. Lemanczyk,Profiles of separations: in graphs, matroids, and beyond, Combinatorica 39 (2019), 37–75, available at arXiv:1110.6207
arXiv 2019
Show all 17 references
-
[8]
Diestel and S.-i
R. Diestel and S.-i. Oum,Tangle-tree duality: in graphs, matroids and beyond, Combinatorica 39 (2019), no. 4, 879–910, available at arXiv:1701.02651
2019 arXiv
-
[9]
Elbracht,Tangles determined by majority vote, Master’s Thesis, 2015
C. Elbracht,Tangles determined by majority vote, Master’s Thesis, 2015. Available online. 6We remark that triple covers in their paper are precisely the witnessing sets here. In fact, they proved a more general result about tangles on bipartitions in a more general setting. Ho...
2015
-
[10]
Elbracht, J
C. Elbracht, J. Kneip, and M. Teegen,Tangles are decided by weighted vertex sets, Advances in Combinatorics (2020), available at arXiv:1811.06821
2020 arXiv
-
[11]
, Trees of tangles in abstract separation systems, Journal of Combinatorial Theory, Series A180 (2021), 105425, available at arXiv:1909.09030
2021 arXiv
-
[12]
2, 297–327, available at arXiv:2005.12122
, Trees of tangles in infinite separation systems, Mathematical Proceedings of the Cambridge Philosophical Society 173 (2022), no. 2, 297–327, available at arXiv:2005.12122
2022 arXiv
-
[13]
Grohe,Tangles and connectivity in graphs, Language and Automata Theory and Applications (2016), 24–41, available at arXiv:1602.04727
M. Grohe,Tangles and connectivity in graphs, Language and Automata Theory and Applications (2016), 24–41, available at arXiv:1602.04727
2016 arXiv
-
[14]
Grohe and P
M. Grohe and P. Schweitzer,Isomorphism testing for graphs of bounded rank width, IEEE 56th Annual Symposium on Foundations of Computer Science (2015), 1010–1029, available at arXiv:1505.03737
2015 arXiv
-
[16]
Robertson and P
N. Robertson and P. D Seymour,Graph minors I–XX, Journal of Combinatorial Theory, Series B (1983–2004)
1983
-
[17]
La Sapienza
, Graph minors. X. Obstructions to tree-decomposition, Journal of Combinatorial Theory, Series B52 (1991), no. 2, 153–190. University of Hamburg, Department of Mathematics, Bundesstraße 55 (Geomatikum), 20146 Hamburg, Germany Email address: {sandra.albrechtsen,hanno.von.bergen...
1991
Reviewed August 12, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.