Skip to content

Local Incidence Lifts Of Fundamental Graphs Are Not Pivot-Robust

Claim/Theorem

Let G_fund(M,B) be a fundamental graph of a binary matroid M with basis-side cut (B,E(M)\setminus B).

Consider any classical load construction \mathcal L(G) derived from a chosen fundamental graph G and measured on the original terminal cut (B,E\setminus B), for example:

  • packet demand crossing that cut,
  • nonnegative hypergraph cut capacity,
  • auxiliary-vertex graph-cut capacity.

Assume the construction is incidence-local in the following weak sense:

there exist constants c_1,c_2>0 such that for every fundamental graph G=(A\sqcup B,E) in the family under consideration,

\[ c_1\,|E(G)| \;\le\; \operatorname{load}_{\mathcal L(G)}(A) \;\le\; c_2\,|E(G)|. \]

Then \mathcal L cannot give a basis-robust constant-factor realization of binary matroid connectivity.

More precisely, there is no universal constant C such that

\[ \frac{1}{C}\,\lambda_M(A) \;\le\; \operatorname{load}_{\mathcal L(G_{\mathrm{fund}}(M,B))}(A) \;\le\; C\,\lambda_M(A) \]

holds simultaneously for all binary matroids M, all bases B, and the basis-side cut A=B.

Proof skeleton:

  1. [[fundamental-graph-edge-cuts-are-basis-unstable.md]] gives a family M_m, namely the cycle matroids of K_m, with two bases B_{\star} and B_{\mathrm{path}} such that
\[ \lambda_{M_m}(B_{\star})=\lambda_{M_m}(B_{\mathrm{path}})=m-2, \]

while

\[ \frac{|E(G_{\mathrm{path}})|}{|E(G_{\star})|} = \frac{(m-1)(m-2)(m+3)/6}{(m-1)(m-2)} = \frac{m+3}{6}, \]

which is unbounded.

  1. By the incidence-local assumption,
\[ \operatorname{load}_{\mathcal L(G_{\star})}(B_{\star})=\Theta(|E(G_{\star})|), \qquad \operatorname{load}_{\mathcal L(G_{\mathrm{path}})}(B_{\mathrm{path}})=\Theta(|E(G_{\mathrm{path}})|). \]

Hence the ratio of these two loads is also unbounded in m.

  1. But if both loads were within a universal constant factor of the same connectivity value m-2, their ratio would be bounded.

This contradiction proves that no incidence-local classical load extracted from a chosen fundamental graph can be basis-robust.

Therefore the natural local gadget routes all fail at once:

  • one packet or one routed demand per incidence edge,
  • bounded-size nonnegative hypergraph gadgets attached edge-by-edge to the incidence graph,
  • bounded-size auxiliary-vertex graph gadgets attached edge-by-edge to the incidence graph.

So any surviving positive route must be genuinely more global than a local replacement of each fundamental-graph incidence edge.

Dependencies

  • [[basis-robust-fundamental-graph-loads-must-be-pivot-invariant.md]]
  • [[fundamental-graph-edge-cuts-are-basis-unstable.md]]
  • [[binary-matroid-connectivity-equals-fundamental-graph-cut-rank.md]]

Conflicts/Gaps

  • This rules out only incidence-local classical constructions. It does not rule out a more global pivot-class construction that uses the whole fundamental-graph equivalence class at once.
  • It does not exclude signed, algebraic, or cancellation-based representations.
  • The obstruction is formulated on the basis-side cut of the chosen fundamental graph; it does not yet exclude every conceivable classical load model on every other derived cut family.

Sources

  • 10.1016/j.jctb.2005.03.003