Skip to content

High Tangle Order Gives Large Tangle-Independent Set

Claim/Theorem

Let \(M\) be a 3-connected matroid, let \(\mathcal T\) be a tangle of \(M\), let \(N\) be a minor of \(M\) with no loops or coloops, and let

\[ t:=\operatorname{rk}_{\mathcal T}(E(N)) \]

in the tangle matroid \(M(\mathcal T)\). If the order of \(\mathcal T\) is at least

\[ 20k+t-13, \]

then there exists a set \(X\subseteq E(M)\) with

\[ |X|=k, \qquad \operatorname{rk}_{\mathcal T}(E(N)\cup X)=t+k, \]

such that one of

\[ M\backslash X \qquad\text{or}\qquad M/X \]

is 3-connected with \(N\) as a minor.

Specializing to the empty minor gives:

if the tangle order is at least 20k-13, then there exists a \(\mathcal T\)-independent set \(X\) of size k such that one of \(M\backslash X\) or \(M/X\) remains 3-connected.

By Lemma 2.29 of the same paper, every \(\mathcal T\)-independent set is both independent and coindependent in \(M\). Therefore high tangle order forces a large set of elements that is simultaneously:

  • independent,
  • coindependent,
  • and globally removable by all-deletion or all-contraction while preserving 3-connectivity.

Using [[tangle-order-equals-branchwidth.md]], the same conclusion applies to any 3-connected matroid of sufficiently large branchwidth.

Dependencies

  • [[tangle-order-equals-branchwidth.md]]

Conflicts/Gaps

  • This theorem produces a large flexible sparse set, not a dense or balanced highly connected set.
  • It does not imply that the set \(X\) lies in a single bag of a lean tree-decomposition, nor that it yields linear cut rank across balanced separators.
  • So the current frontier becomes sharper: high tangle order already gives many removable independent/coindependent elements, but the graph still lacks a theorem concentrating such a set into the kind of dense or bag-local object needed by [[dense-k-connected-set-forces-balanced-cut-rank.md]] or [[lean-matroid-bag-gives-rank-connected-set.md]].

Sources

  • 10.1016/j.jctb.2014.12.003