Michal Salter-Duke (2024), PhD thesis, Te Herenga Waka—Victoria University of Wellington.
Key takeaways
From the reading, NOTE-814.
- What a tangle is. For an order k, a choice of side for every cut of weight below k, such that no three chosen “small sides” cover the graph and no “big side” is a single vertex. It points to a region without listing its vertices. For each k a graph has either such a tangle or a carving of width below k, not both (tangle–tree duality).
- An algorithm. Cuts are enumerated in order of weight (Vazirani–Yannakakis) and oriented by a pruned search. Four proved reductions (hanging trees, small forests, interchangeable leaves) make graphs of about 200 vertices feasible in under a day. It remains exponential.
- Communities. Tangle communities resemble those of standard methods where community structure is strongly delineated (yeast PPI), and not where it is weak: the karate club, C. elegans and college football show one tangle per order at every order reached. Similarity falls as order rises past a network’s best order, and each region seems to have its own best order.
- Trivial tangles. A vertex of degree at least θ that low-order cuts can separate is a tangle of order θ. Groups of one to three vertices recur, often at a network’s periphery.
- Images. In three-shade greyscale a one-pixel-wide line cannot be distinguished by any tangle, except at the image’s edge or corner. One tangle picks out the Mona Lisa’s eye. Higher colour resolution pushes meaningful tangles beyond the orders that can be computed.
- A boundary needs a further rule. Vertices are assigned to a tangle’s community if they lie on the big side of every distinguishing cut, with inheritance from lower orders. That rule is the author’s.
Standing in the record
Filed on 2026-10-12 from the owner’s papers-feed for QUESTION-035, and read on 2026-10-14 in NOTE-814. The seed note called it a rival criterion for when a combined form is one system and where its boundary lies. The thesis tests that criterion and finds it wanting in practice. Tangles see strongly delineated regions. They leave weak structure undivided, pass single high-degree vertices, and give no boundary without an extra assignment rule. THEORY-254 is filed from it. For CLAIM-157 it shows that a single global threshold of strength suits some regions and not others.