Good Classical Codes Have Linear Matroid Pathwidth¶
Claim/Theorem¶
Let \(C\) be an [n,k,d] linear code over a finite field, and let \(M(C)\) be its associated vector matroid. Then
\[
\operatorname{pw}(M(C))
\;\in\;
\Omega\!\left(\frac{k(d-1)}{n}\right).
\]
More explicitly, combining [[good-codes-have-some-linear-cut-rank.md]] with [[matroid-pathwidth-equals-code-trellis-width.md]] gives
\[
\operatorname{pw}(M(C))
\;=\;
\operatorname{tw}_{\mathrm{trellis}}(C)
\;\ge\;
\frac{k(d-1)}{n}.
\]
Therefore every asymptotically good classical code family has linear matroid pathwidth.
Equivalently, every coordinate ordering of a good classical code has some prefix cut whose code or matroid connectivity is linear in blocklength, and the minimum possible such ordering-width remains linear.
Dependencies¶
- [[good-codes-have-some-linear-cut-rank.md]]
- [[matroid-pathwidth-equals-code-trellis-width.md]]
Conflicts/Gaps¶
- This theorem is strong for genuinely good classical codes, but it does not apply to the CSS constituent codes \(C_0=\ker H_0\) and \(C_1=\ker H_1\) of qLDPC constructions, because those codes are not asymptotically good; see [[qldpc-css-constituent-codes-not-good.md]].
- So the node sharpens the ordering route conceptually, but it does not by itself strengthen the Quantum Tanner frontier.
Sources¶
10.48550/arXiv.0705.138410.48550/arXiv.0805.219910.48550/arXiv.0711.1383