Skip to content

Basis-Robust Fundamental-Graph Loads Must Be Pivot-Invariant

Claim/Theorem

For a binary matroid M, the exact graph realization from [[binary-matroid-connectivity-equals-fundamental-graph-cut-rank.md]] is canonical only up to pivot equivalence, not up to any fixed chosen basis.

More precisely:

  1. Oum's Corollary 3.5 (p. 10) shows that any two fundamental graphs of the same binary matroid are related by a sequence of pivotings.
  2. Oum's Proposition 2.6 (p. 7) and Corollary 2.7 (pp. 7-8) show that cut-rank, and hence rank-width, is invariant under the local-complementation moves underlying pivoting.
  3. Therefore the exact binary-matroid realization
\[ \lambda_M(X)=\operatorname{cutrk}_{G_{\mathrm{fund}}(M,B)}(X)+1 \]

depends canonically only on the pivot-equivalence class of fundamental graphs, not on any specific basis graph as a classical load-bearing object.

So any candidate classical load semantics extracted from a chosen fundamental graph and intended to depend only on M up to universal constant factors must at least be stable under pivoting on the class of fundamental graphs of M.

But [[fundamental-graph-edge-cuts-are-basis-unstable.md]] gives a family of binary matroids, namely the cycle matroids of K_m, with two fundamental graphs G_star and G_path satisfying

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

while

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

which is unbounded.

Hence no quantity that is constant-factor comparable to the ordinary incidence load of a chosen fundamental-graph cut can be basis-robust. In particular, this rules out the most naive classical interpretations derived directly from one chosen fundamental graph:

  • ordinary edge-cut capacity of that graph,
  • packet or path models that place one unit of classical demand on each incidence edge of that graph,
  • auxiliary-vertex incidence graphs whose cut load is constant-factor equivalent to the same raw incidence count.

Therefore the live realization gap is narrower still: any successful routing-style CD(T_n,G) interpretation of stabilizer cut rank must either

  • use a more global pivot-invariant construction than a single chosen fundamental graph with raw incidence loads, or
  • abandon this direct classical-load reading entirely.

Dependencies

  • [[binary-matroid-connectivity-equals-fundamental-graph-cut-rank.md]]
  • [[fundamental-graph-edge-cuts-are-basis-unstable.md]]
  • [[cross-cut-stabilizer-rank-rank-formula.md]]

Conflicts/Gaps

  • This does not rule out all hypergraph, packet, or auxiliary-vertex realizations. It rules out only those whose cut load is constant-factor comparable to the raw incidence size of a chosen fundamental graph.
  • It does not exclude constructions built from the whole pivot-equivalence class, signed capacities, or other nonclassical algebraic summaries.
  • The obstruction is demonstrated on cycle matroids of complete graphs, not yet on a Quantum Tanner stabilizer family.

Sources

  • 10.1016/j.jctb.2005.03.003