Skip to content

Tangle-Independent Set Gives Connected Set

Claim/Theorem

Let \(\mathcal T\) be a tangle of order \(k\) in a matroid \(M\), and let \(X\subseteq E(M)\) be independent in the tangle matroid \(M(\mathcal T)\) with

\[ |X|<k-1. \]

Then \(X\) is a cardinality-based connected set in \(M\):

\[ \lambda_M(A)\;\ge\;\min\{|A\cap X|,\ |X-A|\} \]

for every \(A\subseteq E(M)\).

Equivalently, \(X\) is an (|X|+1)-connected set in the sense used by [[tangle-breadth-gives-k-connected-set.md]].

Proof sketch:

  1. Every subset \(Y\subseteq X\) is also independent in \(M(\mathcal T)\).
  2. By Lemma 15(iii) from the source paper, since \(|Y|<k-1\), this means:
  3. \(Y\) is \(\mathcal T\)-small, and
  4. there is no \(\mathcal T\)-small set \(B\supseteq Y\) with
\[ \lambda_M(B)<|Y|. \]
  1. Now let \(A\subseteq E(M)\) and set
\[ s:=\min\{|A\cap X|,\ |X-A|\}. \]

If \(s=0\) the claim is trivial. Assume \(s>0\) and, for contradiction, that

\[ \lambda_M(A)<s. \]

Then in particular \(\lambda_M(A)\le k-2\), so by the tangle axiom exactly one of \(A\) or \(E(M)-A\) is \(\mathcal T\)-small. 4. Whichever side is \(\mathcal T\)-small contains a subset \(Y\subseteq X\) of size \(s\). But then this \(\mathcal T\)-small side is a \(\mathcal T\)-small superset of \(Y\) with connectivity less than \(|Y|=s\), contradicting Step 2.

Hence

\[ \lambda_M(A)\ge s=\min\{|A\cap X|,\ |X-A|\}. \]

So any sufficiently small tangle-independent set is already a genuine connected set, even without any breadth hypothesis.

Dependencies

  • [[tangle-breadth-gives-k-connected-set.md]]

Conflicts/Gaps

  • This yields a connected set whose size is at most the tangle order minus 2, not a dense set spanning a constant fraction of the ground set.
  • The theorem is strongest when one has a source of large tangle-independent sets, such as [[high-tangle-order-gives-large-tangle-independent-set.md]].
  • It does not by itself solve the separator-alignment problem for Conjecture 3, because a connected set of size Omega(n/log n) is still far from the dense linear regime needed by [[dense-k-connected-set-forces-balanced-cut-rank.md]].

Sources

  • 10.37236/12467