Every Matroid Admits Optimal Lean Tree Decomposition

Claim/Theorem

Every matroid \(M\) admits a lean tree-decomposition of width exactly

\[ \operatorname{tw}(M). \]

So after passing from branchwidth to matroid tree-width via [[branchwidth-and-matroid-treewidth-are-equivalent.md]], one may always assume that the optimal tree-decomposition is lean without paying any width penalty.

For the present graph this is the right structural normalization on the intrinsic side: the live issue is not whether an optimal-width decomposition can be made lean, but whether its width can be concentrated into a sufficiently large-rank bag or converted into a usable coordinate cut.

Dependencies

• [[branchwidth-and-matroid-treewidth-are-equivalent.md]]

Conflicts/Gaps

• Lean does not mean that any bag has large rank. It only means local connectivity is represented faithfully inside the decomposition.
• Therefore this theorem sharpens the frontier to a concentration problem, but it does not solve it.

Sources

• 10.1016/j.jctb.2017.12.001