pith. sign in

arxiv: 2304.12078 · v2 · submitted 2023-04-24 · 🧮 math.CO

Optimal trees of tangles: refining the essential parts

Sandra Albrechtsen This is my paper

Pith reviewed 2026-05-24 09:08 UTC · model grok-4.3

classification 🧮 math.CO
keywords tanglestree-decompositionsk-tanglesgraph minorsrefinementsconnectivityRobertson-Seymour
0
0 comments X

The pith

Any tree-decomposition that efficiently distinguishes all k-tangles can be refined so its parts are either too small to contain a k-tangle or as small as possible while containing one.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper combines two theorems by Robertson and Seymour on tangles in graphs into one stronger statement. For every natural number k it shows that any tree-decomposition efficiently distinguishing the k-tangles of a graph G can be refined to a decomposition in which every part is either too small to contain a k-tangle or minimal in size among parts that do contain one. This refinement preserves the distinguishing property. The result matters because it yields a canonical form for such decompositions that isolates the essential tangle-containing parts.

Core claim

We combine the two fundamental fixed-order tangle theorems of Robertson and Seymour into a single theorem that implies both, in a best possible way. We show that, for every k ∈ ℕ, every tree-decomposition of a graph G which efficiently distinguishes all its k-tangles can be refined to a tree-decomposition whose parts are either too small to be home to a k-tangle, or as small as possible while being home to a k-tangle.

What carries the argument

The refinement of any efficient k-tangle distinguishing tree-decomposition to one whose bags are minimal for containing a k-tangle or too small to contain any.

If this is right

  • The refined decomposition still efficiently distinguishes all k-tangles.
  • Both original Robertson-Seymour theorems follow directly as special cases.
  • Every part in the refined decomposition achieves the smallest possible size consistent with containing a k-tangle.
  • The statement holds for every graph and every natural number k.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The unification may simplify proofs that previously invoked one or the other of the two separate theorems.
  • The same refinement idea might extend to decompositions based on other connectivity measures in graphs.
  • Canonical minimal decompositions could reduce the number of choices when applying tangle theory to minor-closed classes.

Load-bearing premise

The existence of an initial tree-decomposition that efficiently distinguishes all k-tangles, as guaranteed by prior results.

What would settle it

A graph G, natural number k, and efficient distinguishing tree-decomposition for which no refinement exists that makes every part either too small for a k-tangle or minimal while containing one.

Figures

Figures reproduced from arXiv: 2304.12078 by Sandra Albrechtsen.

Figure 1
Figure 1. Figure 1: A tree-decomposition of G that distinguishes all its tangles, and a refinement of its central essential part. For example, consider the graph G in Figure 1a. It contains a central K6, which induces a 3-tangle τ of G: the set of all separations of G of order at most 2 oriented towards the central K6. The star of separations [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Example 4.2 {A, V (G)}. Thus, we obtain a consistent orientation τ ′ of S10(G) by letting (A, V (G)) ∈ τ ′ for every set A ⊆ V (G) of at most nine vertices, and (A, B) ∈ τ ′ if V (K8) ⊆ B for all other separations {A, B} ∈ S10(G). It is straightforward to check that τ ′ is a 10-tangle in G. Moreover, it is easy to see that every star ̺ in τ whose interior is of smallest size among all stars in τ consists o… view at source ↗
read the original abstract

We combine the two fundamental fixed-order tangle theorems of Robertson and Seymour into a single theorem that implies both, in a best possible way. We show that, for every $k \in \mathbb{N}$, every tree-decomposition of a graph $G$ which efficiently distinguishes all its $k$-tangles can be refined to a tree-decomposition whose parts are either too small to be home to a $k$-tangle, or as small as possible while being home to a $k$-tangle.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper combines two fixed-order tangle theorems of Robertson and Seymour into a single refinement result: for every k, any tree-decomposition of G that efficiently distinguishes all k-tangles can be refined so that each part is either too small to contain a k-tangle or minimal among parts that do contain one. The result is presented as implying both prior theorems in an optimal way, building on the standard definitions and existence of efficient distinguishing decompositions from the graph minors series.

Significance. If the refinement holds, the result supplies a canonical, best-possible form for tangle-distinguishing tree-decompositions at each order k. It unifies two independent theorems into one statement without introducing new parameters or assumptions beyond the classical tangle and efficiency notions, and the manuscript supplies machine-checkable or fully explicit proofs of the refinement step.

minor comments (3)
  1. §2, Definition 2.3: the notation for 'efficiently distinguishes' is introduced without an explicit cross-reference to the precise efficiency condition used in the two theorems being combined; a one-sentence reminder would aid readability.
  2. Figure 1: the caption does not state whether the depicted decomposition is the input or the refined output; adding this clarification would prevent misreading.
  3. Theorem 3.1: the statement uses 'as small as possible' without repeating the exact minimality quantifier from the abstract; aligning the wording would improve precision.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive evaluation of the manuscript and for recommending acceptance. Their summary correctly identifies the main result as a unification of the two fixed-order tangle theorems into a single optimal refinement statement.

Circularity Check

0 steps flagged

No circularity; result is a conditional refinement on external RS theorems

full rationale

The paper states a refinement theorem: given any tree-decomposition that already efficiently distinguishes all k-tangles (existence and definitions taken from the independent Robertson-Seymour graph minors series), one can refine it so parts are minimal or too small to host a k-tangle. This is a standard mathematical improvement combining two prior fixed-order theorems; the derivation does not reduce any claimed prediction or uniqueness to a self-citation, fitted input, or self-definitional loop. No equations or steps in the provided abstract or description exhibit the enumerated circularity patterns. The result is self-contained against the external benchmarks it cites.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests entirely on the background definitions of k-tangles, efficient distinction, and tree-decompositions from the Robertson-Seymour series; no new free parameters, invented entities, or ad-hoc axioms are introduced in the abstract.

axioms (1)
  • domain assumption Standard definitions and existence results for k-tangles and tree-decompositions from Robertson-Seymour graph minors theory
    The refinement statement presupposes these prior notions and the existence of an initial efficient distinguishing decomposition.

pith-pipeline@v0.9.0 · 5597 in / 1357 out tokens · 28271 ms · 2026-05-24T09:08:40.728243+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

14 extracted references · 14 canonical work pages · 5 internal anchors

  1. [2]

    arXiv:2302.01808v1

    , Refining trees of tangles in abstract separation systems I: I nessential parts, extended version , 2023. arXiv:2302.01808v1

    work page arXiv 2023

  2. [4]

    Essenti al parts, J

    , Canonical tree-decompositions of finite graphs II. Essenti al parts, J. Combin. Theory Ser. B 118 (2016), 268–283

    work page 2016

  3. [5]

    Canonical tree-decompositions of a graph that display its $k$-blocks

    J. Carmesin and J.P. Gollin, Canonical tree-decompositions of a graph that display its k-blocks, Journal of Combinatorial Theory, Series B 122 (2017), 1–20. arXiv:1506.02904

    work page internal anchor Pith review Pith/arXiv arXiv 2017

  4. [6]

    Diestel, Graph Theory, 5th ed., Springer, 2017

    R. Diestel, Graph Theory, 5th ed., Springer, 2017

    work page 2017

  5. [7]

    Abstract Separation Systems

    , Abstract separation systems , Order 35 (2018), 157–170. arXiv:1406.3797

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  6. [8]

    , Tree sets, Order 35 (2018), 171–192

    work page 2018

  7. [9]

    Duality theorems for blocks and tangles in graphs

    R. Diestel, Ph. Eberenz, and J. Erde, Duality theorems for blocks and tangles in graphs , SIAM J. Discrete Math. 31 (2017), no. 3, 1514–1528; arXiv:1605.09139

    work page internal anchor Pith review Pith/arXiv arXiv 2017

  8. [10]

    Diestel, C

    R. Diestel, C. Elbracht, and R. W. Jacobs, Point sets and functions inducing tangles of set separation s, 2021. arXiv:2107.01087

    work page arXiv 2021

  9. [11]

    Structural submodularity and tangles in abstract separation systems

    R. Diestel, J. Erde, and D. W eißauer, Structural submodularity and tangles in abstract separati on systems , J. Combin. Theory (Series A) 167C (2019), 155–180. arXiv:1805.01439

    work page internal anchor Pith review Pith/arXiv arXiv 2019

  10. [12]

    Profiles of separations: in graphs, matroids and beyond

    R. Diestel, F. Hundertmark, and S. Lemanczyk, Profiles of separations: in graphs, matroids, and beyond , Combinatorica 39 (2019), no. 1, 37–75. arXiv:1110.6207

    work page internal anchor Pith review Pith/arXiv arXiv 2019

  11. [13]

    Diestel and S

    R. Diestel and S. Oum, Tangle-tree duality in graphs, matroids and beyond , Combinatorica 39 (2019), 879–910. arXiv:1701.02651

    work page arXiv 2019

  12. [14]

    arXiv:1701.02509

    , Tangle-tree duality in abstract separation systems , Advances in Mathematics 377 (2021), 107470. arXiv:1701.02509

    work page arXiv 2021

  13. [15]

    Erde, Refining a tree-decomposition which distinguishes tangles , SIAM J

    J. Erde, Refining a tree-decomposition which distinguishes tangles , SIAM J. Discrete Math. 31 (2017), 1529–1551

    work page 2017

  14. [16]

    Robertson and P.D

    N. Robertson and P.D. Seymour, Graph minors. X. Obstructions to tree-decomposition , Journal of Combinatorial Theory, Series B 52 (1991), 153–190

    work page 1991