Sufficiently Dense k-Connected Set Forces Branchwidth¶

Claim/Theorem¶

Keep the notation of [[dense-k-connected-set-forces-balanced-cut-rank.md]], [[large-k-connected-set-gives-balanced-cut-rank.md]], and [[tangle-order-equals-branchwidth.md]].

There is a concrete conditional route from dense connected-set concentration to linear-order tangles.

Let \(M\) be a matroid on a ground set \(E\) of size \(n\), and suppose \(M\) contains a \(k\)-connected set \(Z \subseteq E\) of size

\[ t := |Z| > \frac{2n}{3} + k - 2. \]

Then

\[ \operatorname{bw}(M) \ge k - 1. \]

Equivalently, by [[tangle-order-equals-branchwidth.md]], \(M\) has a tangle of order at least \(k - 1\).

Hence for any target family of original qubit parity-check matroids \(M_n\) on qubit sets \(Q_n\), the following explicit mechanism is sufficient for

\[ H_{\mathrm{tan}}^{\Omega}: \quad M_n \text{ has a tangle of order } \Omega(|Q_n|). \]

It is enough to prove that there are sets \(Z_n \subseteq Q_n\) and integers \(k_n\) such that

\[ Z_n \text{ is } k_n\text{-connected in } M_n, \qquad k_n = \Omega(|Q_n|), \qquad |Z_n| > \frac{2|Q_n|}{3} + k_n - 2. \]

Proof.

Let \((T,\mu)\) be any cubic branch decomposition of \(M\).
Elementary centroid-edge fact for cubic leaf-labeled trees:

there exists an edge \(e \in E(T)\) such that the displayed leaf set \(L_e \subseteq E\) satisfies

\[ \frac{n}{3} \le |L_e| \le \frac{2n}{3}. \]

Indeed, if every edge had one side of size strictly less than \(n/3\), orient each edge toward the side with more than \(2n/3\) leaves. A sink vertex would then have all incident complementary components of size less than \(n/3\), impossible because their union contains all \(n\) leaves.
The cut \(L_e\) is therefore 1/3-balanced on the full ground set. Applying [[dense-k-connected-set-forces-balanced-cut-rank.md]] with \(\beta = 1/3\) gives

\[ \lambda_M(L_e) \ge k - 1, \]

because \(|Z| > (1-\beta)n + k - 2 = 2n/3 + k - 2\).
Hence the width of \((T,\mu)\) is at least \(k - 1\). Since the branch decomposition was arbitrary,

\[ \operatorname{bw}(M) \ge k - 1. \]
Finally, [[tangle-order-equals-branchwidth.md]] converts this to a tangle of order at least \(k - 1\).

So the branchwidth subroute is now reduced to one explicit dense connected-set concentration statement. A sufficiently dense linear-size, linearly connected set in the original qubit parity-check matroid is enough to force linear branchwidth and hence linear-order tangles.

Dependencies¶

[[dense-k-connected-set-forces-balanced-cut-rank.md]]
[[large-k-connected-set-gives-balanced-cut-rank.md]]
[[tangle-order-equals-branchwidth.md]]

Conflicts/Gaps¶

This node does not show that the current Quantum Tanner / left-right-Cayley source package produces such sets \(Z_n\).
The hypothesis is stronger than merely having some linear-size, linearly connected set. The set must also be dense enough to be cut on both sides by the generic 1/3-balanced displayed edge of an arbitrary branch decomposition.
Therefore this is a conditional reduction for the chosen mechanism branchwidth-from dense connected-set concentration, not a closure theorem for the target family.
The node does not supersede [[dense-tangle-breadth-is-the-canonical-remaining-intrinsic-target.md]]. It identifies one concrete subordinate route by which dense connected-set concentration would already imply H_{\mathrm{tan}}^{\Omega}.

Sources¶

10.37236/12467
10.48550/arXiv.2109.14599
10.48550/arXiv.0805.2199
10.1016/j.jctb.2007.10.008