Tangles are Decided by Weighted Vertex Sets

Abstract

We show that, given a $k$-tangle $\tau$ in a graph $G$, there always exists a weight function $w:V(G)\to \mathbb{N}$ such that a separation $(A,B)$ of $G$ of order $<k$ lies in $\tau$ if and only if $w(A)<w(B)$, where $w(U):={\sum }_{u\in U}w(u)$ for $U\subseteq V(G)$. We show that the same result holds also for tangles of hypergraphs as well as for edge-tangles of graphs, but not for edge-tangles of hypergraphs.

arXiv comment9 pages. Journal version, includes new section on edge tangles