Skip to content

Tangle Order Equals Branchwidth

Claim/Theorem

For any matroid \(M\), the maximum order of a tangle in \(M\) is exactly the branchwidth of \(M\).

Equivalently, for a binary linear code \(C\) viewed through its associated binary matroid, code branchwidth can be read as the largest order of a tangle of the connectivity function

\[ \lambda_C(J)=\dim(C|_J)+\dim(C|_{J^c})-\dim(C). \]

So branchwidth is not just a minimax over tree decompositions. It also has an intrinsic dual description as the order of a coherent family of highly connected sides of low-order separations.

Dependencies

  • None.

Conflicts/Gaps

  • This node translates branchwidth into tangle language, but does not itself produce balanced cuts or hardware-aligned cuts.
  • The theorem is matroid-theoretic, so applying it to stabilizer spaces still proceeds through the associated binary code or parity-check matroid.
  • By itself it does not strengthen the existing Omega(n/log n) branchwidth bound; it only provides a new way to localize that width.

Sources

  • 10.1016/j.jctb.2007.10.008