Skip to content

Large k-Connected Set Generates An Order-k Tangle

Claim/Theorem

Keep the notation of [[tangle-breadth-gives-k-connected-set.md]].

Let M be a matroid and let Z \subseteq E(M) be a k-connected set of size

\[ t := |Z| \ge 3k - 5 \]

with k \ge 3.

Then there exists a tangle \mathcal T_Z of order k in M such that

\[ M_{\mathcal T_Z}|Z \cong U_{k-1,t}. \]

Consequently:

  1. \mathcal T_Z is generated by the set Z in the sense of the source paper.

  2. The breadth of \mathcal T_Z is at least t.

  3. Combined with [[tangle-breadth-gives-k-connected-set.md]], the two notions become equivalent above the threshold 3k-5:

    • any tangle of order k and breadth t gives a t-element k-connected set;
    • any t-element k-connected set with t\ge 3k-5 generates an order-k tangle whose breadth is at least t.

Proof.

  1. By Lemma 18 of 10.37236/12467, if Z is a k-connected set with k\ge 3 and |Z|\ge 3k-5, then the collection

    \[ \mathcal T_Z := \{A\subseteq E(M) : \lambda_M(A)\le k-2 \text{ and } |A\cap Z|\le k-2\} \]

    is a tangle of order k, and its tangle matroid satisfies

    \[ M_{\mathcal T_Z}|Z \cong U_{k-1,t}. \]

  2. Since a tangle matroid of order k has rank k-1, the restriction above is a spanning uniform restriction of M_{\mathcal T_Z}. Therefore, by definition of breadth,

    \[ \operatorname{breadth}(\mathcal T_Z)\ge t. \]

  3. The forward direction is [[tangle-breadth-gives-k-connected-set.md]]. The converse direction is Step 1, and generation by Z is exactly the source-paper terminology following Lemma 18.

So beyond the threshold 3k-5, a large k-connected set is not merely a shadow of tangle breadth. It reconstructs an order-k tangle carrying uniform spanning mass on the same set.

Dependencies

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

Conflicts/Gaps

  • This theorem does not by itself imply balanced cut rank. Density of Z inside the full ground set is still needed to align the connected set with hardware-balanced cuts.
  • The theorem gives breadth at least |Z|, not necessarily a precise equality statement.
  • It does not produce a weakly 4-connected minor or a robustness theorem; it stays in the original matroid and only reconstructs the tangle from a sufficiently large k-connected set.

Sources

  • 10.37236/12467