Skip to content

Fundamental Graph Edge Cuts Are Basis-Unstable

Claim/Theorem

The exact binary-matroid realization of connectivity by fundamental-graph cut-rank does not canonically descend to classical edge-cut capacity on the same graph.

More precisely, there is a family of binary matroids for which different choices of basis produce fundamental graphs with the same exact connectivity function but with basis-partition edge cuts differing by an unbounded factor.

Take \(M_m\) to be the cycle matroid of the complete graph \(K_m\) for \(m\ge 4\).

Basis 1: star basis

Let \(B_{\star}\) be the star spanning tree centered at vertex 1. Its fundamental graph \(G_{\star}\) has

  • left side B_{\star} consisting of the m-1 star edges (1,i),
  • right side E(K_m)\setminus B_{\star} consisting of the \binom{m-1}{2} remaining edges (i,j),
  • each right vertex adjacent to exactly the two star edges (1,i) and (1,j).

Therefore

\[ |\delta_{G_{\star}}(B_{\star})| = 2\binom{m-1}{2} =(m-1)(m-2). \]

Basis 2: path basis

Let \(B_{\mathrm{path}}\) be the Hamilton path spanning tree with edges (i,i+1), 1\le i\le m-1. Its fundamental graph \(G_{\mathrm{path}}\) has

  • left side B_{\mathrm{path}},
  • right side the non-tree edges (i,j) with j\ge i+2,
  • each right vertex (i,j) adjacent to the j-i tree edges along the path from i to j.

Hence

\[ |\delta_{G_{\mathrm{path}}}(B_{\mathrm{path}})| = \sum_{d=2}^{m-1} d(m-d) = \frac{(m-1)(m-2)(m+3)}{6}. \]

So the ratio of these basis-partition edge cuts is

\[ \frac{|\delta_{G_{\mathrm{path}}}(B_{\mathrm{path}})|} {|\delta_{G_{\star}}(B_{\star})|} = \frac{m+3}{6}, \]

which is unbounded in \(m\).

But the underlying binary matroid is the same. Therefore its connectivity value across the basis side is the same in both realizations. By Oum's Proposition 3.1,

\[ \lambda_{M_m}(B_{\star}) = \operatorname{cutrk}_{G_{\star}}(B_{\star})+1, \qquad \lambda_{M_m}(B_{\mathrm{path}}) = \operatorname{cutrk}_{G_{\mathrm{path}}}(B_{\mathrm{path}})+1. \]

For the cycle matroid of K_m, one has

\[ \lambda_{M_m}(B_{\star}) = \lambda_{M_m}(B_{\mathrm{path}}) = m-2, \]

because each basis has rank m-1, the whole matroid has rank m-1, and the complement of any spanning tree in K_m has rank m-2. Therefore

\[ \operatorname{cutrk}_{G_{\star}}(B_{\star}) = \operatorname{cutrk}_{G_{\mathrm{path}}}(B_{\mathrm{path}}) = m-3, \]

while the corresponding classical edge cuts differ by the unbounded factor (m+3)/6.

Therefore no uniform constant-factor theorem can convert the exact fundamental-graph cut-rank realization into the ordinary edge-cut capacity of that same fundamental graph in any basis-independent way.

This gives a sharp obstruction to the most naive classical routing interpretation of [[binary-matroid-connectivity-equals-fundamental-graph-cut-rank.md]]:

  • exact binary realization by graph cut-rank exists,
  • but raw edge-load or edge-capacity semantics of the fundamental graph are unstable under basis change.

So any successful routing-style CD(T_n,G) theorem for stabilizer cut rank must do more than pick a basis and read off ordinary cuts of the resulting fundamental graph.

Dependencies

  • [[binary-matroid-connectivity-equals-fundamental-graph-cut-rank.md]]
  • [[cross-cut-stabilizer-rank-rank-formula.md]]
  • [[stabilizer-cut-rank-is-not-a-graph-cut-function.md]]

Conflicts/Gaps

  • This rules out only the most direct descent from cut-rank to ordinary edge-cut capacity on the same fundamental graph.
  • It does not rule out the possibility that some carefully chosen basis, auxiliary construction, or different graph/hypergraph realization could recover classical routing semantics.
  • The example uses cycle matroids of complete graphs, not yet stabilizer spaces arising from the Quantum Tanner route.
  • The obstruction is to constant-factor edge-cut interpretation, not to the exact algebraic cut-rank realization itself.

Sources

  • 10.1016/j.jctb.2005.03.003