Skip to content

Pivot-Class Best Incidence Load Still Overestimates Connectivity

Claim/Theorem

Let M_m be the cycle matroid of the complete graph K_m, and for each basis B let

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

be the corresponding fundamental graph.

Define the raw incidence load of a chosen representative by

\[ \iota(M_m,B):=\left|E\!\left(G_{\mathrm{fund}}(M_m,B)\right)\right|. \]

Then even after optimizing over the entire pivot-equivalence class of fundamental graphs, the best incidence load is still much larger than the binary-matroid connectivity scale:

\[ \min_B \iota(M_m,B)=(m-1)(m-2), \qquad \lambda_{M_m}(B)=m-2 \quad\text{for every basis }B, \]

and therefore

\[ \frac{\min_B \iota(M_m,B)}{\lambda_{M_m}(B)}=m-1. \]

So even the best choice of basis leaves a linear-factor gap between raw fundamental-graph incidence and the algebraic connectivity value.

Proof skeleton:

  1. For a spanning-tree basis B=T, each non-tree edge uv contributes to the fundamental graph one incidence for every tree edge on the unique T-path from u to v. Hence

    \[ \iota(M_m,T) = \sum_{uv\notin T} d_T(u,v), \]

    where d_T is tree distance.

  2. Let

    \[ W(T):=\sum_{u<v} d_T(u,v) \]

    be the Wiener index of the tree T. Since tree edges themselves contribute distance 1,

    \[ \iota(M_m,T)=W(T)-(m-1). \]

  3. Using the standard edge-cut expression for tree distances,

    \[ W(T)=\sum_{e\in E(T)} s_e(m-s_e), \]

    where s_e is the size of one component of T\setminus e.

  4. For every 1\le s_e\le m-1,

    \[ s_e(m-s_e)\ge m-1, \]

    with equality iff s_e=1 or m-1.

  5. Since T has m-1 edges,

    \[ W(T)\ge (m-1)^2, \]

    with equality exactly for a star tree. Therefore

    \[ \iota(M_m,T)\ge (m-1)^2-(m-1)=(m-1)(m-2), \]

    and the star basis attains equality.

  6. Meanwhile [[fundamental-graph-edge-cuts-are-basis-unstable.md]] already shows that for every spanning-tree basis B,

    \[ \lambda_{M_m}(B)=m-2. \]

    Combining the two formulas yields the claimed ratio m-1.

Consequences:

  • choosing the best basis inside the whole pivot class still does not recover the connectivity scale;
  • taking averages, medians, maxima, or any other monotone aggregate of incidence-local loads over the pivot class cannot do better;
  • any successful pivot-robust classical interpretation must therefore use a genuinely more global construction than optimizing an incidence-local model over all representatives.

This is strictly sharper than [[basis-robust-fundamental-graph-loads-must-be-pivot-invariant.md]] and [[local-incidence-lifts-of-fundamental-graphs-are-not-pivot-robust.md]]: those nodes rule out fixed-basis and local-gadget routes, while the present node rules out the whole "search over the pivot class for the best classical incidence model" strategy.

Dependencies

  • [[local-incidence-lifts-of-fundamental-graphs-are-not-pivot-robust.md]]
  • [[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 obstruction still targets incidence-local classical loads and their monotone aggregates over the pivot class.
  • It does not rule out a global construction that is not controlled, even up to constants, by incidence sizes of individual representatives.
  • The example is again the cycle matroid of K_m, not yet a stabilizer family from the Quantum Tanner route.

Sources

  • 10.1016/j.jctb.2005.03.003