Skip to content

Linked Branch Decomposition Exists At Optimal Width

Claim/Theorem

Let \(\lambda\) be an integer-valued symmetric submodular function on a finite set \(S\), and let

\[ \operatorname{bw}(\lambda)=n. \]

Then there exists a linked branch decomposition of \(\lambda\) of width exactly \(n\).

Specializing to the connectivity function of a matroid or linear code gives:

  • every matroid \(M\) has a linked branch decomposition of width \(\operatorname{bw}(M)\);
  • every linear code \(C\) has a linked branch decomposition of width equal to its code branchwidth.

So branchwidth is not merely witnessed by some optimal cubic tree on the coordinates. It can always be witnessed by an optimal tree that also satisfies the matroidal analogue of a linkage theorem along every pair of decomposition edges.

Dependencies

  • [[good-codes-have-logarithmic-branchwidth.md]]

Conflicts/Gaps

  • Linkedness is a structural refinement of an optimal branch decomposition. By itself it does not force a balanced displayed cut or a dense connected set.
  • For Conjecture 3, the live question is whether this stronger optimal decomposition can be combined with the new connected-set nodes to force a hardware-relevant large cut in the original parity-check matroid, rather than only in a minor or an abstract decomposition.

Sources

  • 10.1006/jctb.2001.2082