Dense k-Connected Set Forces Balanced Cut Rank

Claim/Theorem

Let \(M\) be a binary matroid, or equivalently the column matroid of a full-row-rank binary matrix, on a ground set \(E\) of size \(n\). Fix a balance parameter \(0<\beta\le 1/2\). Suppose \(Z\subseteq E\) is a \(k\)-connected set of size

\[ |Z|=t \]

in the sense of [[large-k-connected-set-gives-balanced-cut-rank.md]], and assume

\[ t>(1-\beta)n+k-2. \]

Then every \(\beta\)-balanced cut \(L\subseteq E\), meaning

\[ \beta n \le |L| \le (1-\beta)n, \]

satisfies

\[ \lambda_M(L)\ge k-1. \]

Equivalently, if \(M\) is the column matroid of a stabilizer matrix for a stabilizer space \(\mathcal S\), then every \(\beta\)-balanced qubit cut satisfies

\[ \chi_L(\mathcal S)\ge k-1. \]

Combining this with [[stabilizer-cut-rank-functional.md]] yields

\[ \operatorname{depth}(C)\ge \Omega\!\left(\frac{k}{|\partial L|}\right) \]

for any hardware family whose bottleneck separator cuts are \(\beta\)-balanced.

Proof sketch:

1. Since \(|E-L|\le (1-\beta)n\),

\[ |L\cap Z|\ge |Z|-|E-L| \ge t-(1-\beta)n > k-2. \]

1. By symmetry,

\[ |Z-L|\ge t-(1-\beta)n > k-2. \]

1. Applying the \(k\)-connected-set inequality from [[large-k-connected-set-gives-balanced-cut-rank.md]] gives

\[ \lambda_M(L)\ge \min\{|L\cap Z|,\ |Z-L|,\ k-1\}=k-1. \]

So once the highly connected set is dense enough, the old alignment gap disappears: every hardware-balanced cut automatically splits that set on both sides by at least k-1 elements.

Dependencies

• [[large-k-connected-set-gives-balanced-cut-rank.md]]
• [[stabilizer-cut-rank-functional.md]]

Conflicts/Gaps

• This is a sufficient condition, not yet a theorem about Quantum Tanner parity-check matroids.
• It requires a dense \(k\)-connected set, stronger than merely having some large \(k\)-connected set somewhere in the matroid.
• The live intrinsic gap can now be stated more sharply: prove that the relevant Quantum Tanner parity-check matroid contains a \(k\)-connected set \(Z\) with both \(k=\Omega(n)\) and density \(|Z|/n\) above the hardware balance threshold.

Sources

• 10.37236/12467
• 10.48550/arXiv.2109.14599
• 10.48550/arXiv.0805.2199