High Tangle Order Gives Large Connected Set¶
Claim/Theorem¶
Let \(M\) be a 3-connected matroid with a tangle of order \(\theta\). Then for every integer \(m\) with
\[
\theta\ge 20m-13,
\]
\(M\) contains a connected set \(X\) of size m satisfying
\[
\lambda_M(A)\;\ge\;\min\{|A\cap X|,\ |X-A|\}
\]
for all \(A\subseteq E(M)\).
Equivalently, \(X\) is an (m+1)-connected set in the sense of [[tangle-breadth-gives-k-connected-set.md]].
Proof:
- By [[high-tangle-order-gives-large-tangle-independent-set.md]], under the same order hypothesis there exists a \(\mathcal T\)-independent set \(X\) of size
m. - By [[tangle-independent-set-gives-connected-set.md]], any such \(X\) is a connected set.
Using [[tangle-order-equals-branchwidth.md]], the same statement can be rephrased in branchwidth language:
if a 3-connected matroid has branchwidth bw(M), then it contains a connected set of size
\[
\Omega(\operatorname{bw}(M)).
\]
This is a real upgrade over the earlier intrinsic route: high width no longer gives only an abstract large tangle or a removable independent/coindependent set, but an actual cardinality-based connected set in the original 3-connected matroid.
Dependencies¶
- [[high-tangle-order-gives-large-tangle-independent-set.md]]
- [[tangle-independent-set-gives-connected-set.md]]
- [[tangle-order-equals-branchwidth.md]]
Conflicts/Gaps¶
- The connected set obtained here has size only
Omega(branchwidth). For good codes this is still onlyOmega(n/log n), not a dense linear fraction of the ground set. - The theorem requires
3-connectivity. For Conjecture 3 this is currently accessed only after passing to the weakly4-connected minor route, so there remains a minor-versus-original-matroid gap. - Therefore the new theorem materially strengthens the intrinsic route but still falls short of the dense linear connected set needed to close the separator-alignment gap outright.
Sources¶
10.1016/j.jctb.2014.12.00310.37236/12467