Skip to content

Selector Quotient Is Not A Submodular Minor Of Connected Family

Claim/Theorem

Let M be a member of the connected multi-parallel-circuit family from [[multiple-parallel-classes-on-one-circuit-give-connected-cut-rank-at-least-three-family.md]], and let

\[ f_M(L):=\lambda_M(L) \]

be its cut-rank or matroid-connectivity function on the original ground-set bits.

Then the nonexpressible selector

\[ g(u,C,D)=(1-u)C+uD \]

from [[selected-or-selector-is-not-hidden-vertex-graph-cut-expressible.md]] is not obtained from f_M by any standard submodularity-preserving minor operation such as pinning coordinates and minimizing over the others.

More precisely:

  1. f_M is symmetric submodular on the original ground-set lattice.
  2. Every function obtained from f_M by pinning coordinates and minimizing over the remaining visible coordinates is still submodular.
  3. The compression
\[ L\longmapsto (\varepsilon_L,C(L),D(L)) \]

used in [[multi-parallel-circuit-connected-family-reduces-to-selected-or-selector.md]] is not a lattice-homomorphic minor map. In particular, it can destroy submodularity and produce the non-submodular selector quotient g.

Therefore the selector theorem does not by itself lift to a family-level nonexpressibility theorem for the whole connected multi-parallel-circuit family. Any such theorem must use a more global obstruction than visible-submodularity closure under minors.

This is a derived frontier-clarification statement.

  1. By [[multiple-parallel-classes-on-one-circuit-give-connected-cut-rank-at-least-three-family.md]], f_M(L)=\lambda_M(L). By [[stabilizer-cut-rank-defines-canonical-submodular-cd-object.md]], every matroid connectivity function is symmetric submodular, so f_M is submodular.
  2. Pinning variables is just restriction to a subcube, which preserves submodularity. Minimization over remaining visible variables preserves submodularity by [[minimizing-hidden-binary-submodular-energy-preserves-submodularity.md]].
  3. Hence any function produced from f_M by those standard expressive-class closure operations must remain submodular.
  4. But [[selected-or-selector-is-not-hidden-vertex-graph-cut-expressible.md]] shows that g is not submodular. So g cannot arise from f_M by such closure-preserving reductions.
  5. The reason is that the compression to (u,C,D) is not a lattice-homomorphic minor map. For any class P_i with |P_i|\ge 2, choose distinct elements a,b\in P_i. Then
\[ C(\{a\})=0,\qquad C(\{b\})=0,\qquad C(\{a\}\cup\{b\})=1. \]

So the join of two cuts can change C in a way not determined by the joins of their compressed images. The same kind of failure holds dually for D. 6. Thus the selector quotient is a coarse nonlinear summary of the family, not a minor in any closure-compatible sense relevant to hidden-vertex expressibility.

Consequences for the current frontier:

  • the selector theorem is still load-bearing, because it closes the most obvious compressed-state positive route;
  • but it does not settle the full connected regime, because the full family remains inside the submodular world while the selector quotient leaves it;
  • any family-level nonexpressibility theorem must use a stronger obstruction than visible non-submodularity under pinning/minimization closures;
  • any positive theorem must build a more global hidden-vertex construction that keeps enough within-class structure to avoid collapsing to the forbidden selector quotient.

Dependencies

  • [[multiple-parallel-classes-on-one-circuit-give-connected-cut-rank-at-least-three-family.md]]
  • [[stabilizer-cut-rank-defines-canonical-submodular-cd-object.md]]
  • [[minimizing-hidden-binary-submodular-energy-preserves-submodularity.md]]
  • [[selected-or-selector-is-not-hidden-vertex-graph-cut-expressible.md]]

Conflicts/Gaps

  • This node does not prove that the connected family is hidden-vertex graph-cut representable.
  • It also does not prove family-level nonexpressibility.
  • It proves only that the current selector obstruction is quotient-level rather than minor-level, so one cannot lift it to the whole family by the standard closure operations already on disk.
  • Even a future whole-family positive or negative theorem would still need a separate argument to connect hidden-vertex realizability to routing-style CD(T_n,G) semantics.

Sources

  • 10.1109/TIT.2009.2030492
  • 10.1016/j.dam.2009.07.001
  • 10.1007/s10878-017-0136-y
  • Kashyap 2008 preprint: A Decomposition Theory for Binary Linear Codes