Good Codes Have Logarithmic Matroid Treewidth¶

Claim/Theorem¶

Let \(C\) be an [n,k,d] binary linear code and let \(M_C\) be its associated binary matroid. Then

\[ \operatorname{tw}(M_C)\in \Omega\!\left(\frac{k(d-1)}{n\log n}\right). \]

More explicitly, if \(\operatorname{bw}(M_C)\) denotes the code branchwidth of \(C\), then by [[good-codes-have-logarithmic-branchwidth.md]]

\[ \operatorname{bw}(M_C)\in \Omega\!\left(\frac{k(d-1)}{n\log n}\right), \]

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

\[ \operatorname{tw}(M_C)\ge \operatorname{bw}(M_C)-1. \]

Therefore every asymptotically good code family already has intrinsic matroid tree-width Omega(n/log n).

This is the cleanest direct bridge from code parameters to the lean-decomposition side of the current Conjecture 3 frontier.

This theorem still does not identify a large-rank bag, a dense connected set, or a balanced coordinate cut of comparable connectivity.
It is therefore a width theorem, not yet a separator-aligned cut-rank theorem.