Skip to content

Binary Matroid Connectivity Equals Fundamental Graph Cut-Rank

Claim/Theorem

Let \(M\) be a binary matroid on ground set \(E\), choose a basis \(B\subseteq E\), and let

\[ G_{\mathrm{fund}}(M,B) \]

be the corresponding fundamental graph, the bipartite graph on vertex set \(E=B\sqcup(E\setminus B)\) in which

  • vertices are matroid elements, and
  • \(e\in B\) is adjacent to \(f\in E\setminus B\) exactly when \(e\) lies in the fundamental circuit of \(f\) with respect to \(B\).

Then Oum's Proposition 3.1 (p. 9) gives the exact identity

\[ \lambda_M(X)=\operatorname{cutrk}_{G_{\mathrm{fund}}(M,B)}(X)+1 \qquad \text{for every }X\subseteq E, \]

where \(\operatorname{cutrk}_G(X)\) is the binary rank of the adjacency submatrix across the cut \((X,E\setminus X)\).

Equivalently, binary matroid connectivity has an exact graph-theoretic realization, but the graph invariant is cut-rank, not cut capacity.

Applying [[cross-cut-stabilizer-rank-rank-formula.md]] to a full-row-rank stabilizer matrix \(H\) with column matroid \(M_H\), one gets:

for every stabilizer space \(\mathcal S\) on qubit set \(Q\) and every choice of column basis \(B\) of \(M_H\), the fundamental graph

\[ G_{\mathrm{fund}}(H,B) \]

on the same qubit set satisfies

\[ \chi_L(\mathcal S) = \lambda_{M_H}(L) = \operatorname{cutrk}_{G_{\mathrm{fund}}(H,B)}(L)+1 \qquad \text{for every }L\subseteq Q. \]

Oum's Corollary 3.2 (p. 9) then gives

\[ \operatorname{bw}(M_H)=\operatorname{rwd}(G_{\mathrm{fund}}(H,B))+1. \]

So the binary or stabilizer subclass does admit an exact graph realization unavailable for arbitrary matroids. But this realization is algebraic rather than classical: it packages \(\chi_L\) as graph cut-rank, not as numbers of crossing edges, packets, or routed paths.

This is therefore the precise positive theorem available at the current frontier:

  • generic symmetric submodular demands need not admit good classical realizations;
  • generic matroid connectivity still need not admit good hypergraph realizations;
  • binary matroid connectivity, and hence stabilizer cut rank, does admit an exact realization by graph cut-rank on a fundamental graph.

The remaining gap is now sharp: determine whether this exact graph cut-rank realization can itself be converted into any classical routing, packet, guest-graph, or nonnegative-capacity statement strong enough for the desired CD(T_n,G) interpretation.

Dependencies

  • [[cross-cut-stabilizer-rank-rank-formula.md]]
  • [[matroid-connectivity-does-not-force-hypergraph-approximation.md]]
  • [[generic-submodular-demand-does-not-force-classical-routing-realization.md]]

Conflicts/Gaps

  • The realization depends on a chosen basis and hence on a chosen fundamental graph; it is exact but not canonical in the same sense as [[stabilizer-cut-rank-defines-canonical-submodular-cd-object.md]].
  • Graph cut-rank is an algebraic rank over GF(2), not a nonnegative edge-cut capacity. So this theorem still does not provide packet-routing, congestion, or path semantics.
  • Oum's theorem is about binary matroids in general. It does not show that the associated fundamental graphs of stabilizer matroids have any extra geometric or routing structure.
  • This exact graph realization does not contradict [[stabilizer-cut-rank-is-not-a-graph-cut-function.md]], because that node rules out representation by ordinary weighted graph edge cuts, not by graph cut-rank.

Sources

  • 10.1016/j.jctb.2005.03.003
  • 10.48550/arXiv.2109.14599