Branchwidth And Matroid Treewidth Are Equivalent

Claim/Theorem

Let \(M\) be a matroid of tree-width \(k\) and branchwidth \(b\). Then

\[ b-1\le k\le \max\{2b-2,1\}. \]

Hence bounded branchwidth and bounded matroid tree-width are equivalent notions up to constant factors.

In particular:

• every lower bound on branchwidth immediately gives a lower bound of the same order on matroid tree-width;
• every optimal-width tree-decomposition theorem for matroid tree-width becomes available once one knows a branchwidth lower bound.

This is the precise bridge from the existing good-code branchwidth route to the newer lean-decomposition route.

Dependencies

• None.

Conflicts/Gaps

• This theorem compares two width parameters, but it does not say where the width is concentrated inside an optimal tree-decomposition.
• For the Conjecture 3 frontier, the real missing step is still concentration: large matroid tree-width does not by itself force a large-rank bag or a hardware-balanced cut of large intrinsic connectivity.

Sources

• 10.1016/j.ejc.2006.06.005