Skip to content

Multi-Parallel-Circuit Connected Family Reduces To Selected-OR Selector

Claim/Theorem

Let M be the binary matroid from [[multiple-parallel-classes-on-one-circuit-give-connected-cut-rank-at-least-three-family.md]], with ground set

\[ E=P_1\sqcup\cdots\sqcup P_t\sqcup\{u\}. \]

For a cut L\subseteq E, write

\[ p_i(L):=|L\cap P_i|, \qquad \varepsilon_L:=\mathbf 1[u\in L], \]

and define the compressed statistics

\[ M_i(L):=\mathbf 1[0<p_i(L)<|P_i|], \]
\[ C(L):=\mathbf 1[\exists i:\ p_i(L)=|P_i|], \qquad D(L):=\mathbf 1[\exists i:\ p_i(L)=0]. \]

Then

\[ \lambda_M(L) = \sum_{i=1}^t M_i(L) + (1-\varepsilon_L)C(L) + \varepsilon_L D(L). \]

Equivalently, the first connected post-gluing family from [[multiple-parallel-classes-on-one-circuit-give-connected-cut-rank-at-least-three-family.md]] factors exactly into

  1. a sum of independent per-group split indicators M_i, and

  2. one ternary selector

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

This isolates the only genuinely new ingredient beyond the old threshold-lift pieces: the selected-OR gadget g.

Moreover, [[selected-or-selector-is-not-hidden-vertex-graph-cut-expressible.md]] shows that g is not expressible by binary submodular functions with auxiliary variables at all. So the obvious compression-first extension of the hidden-vertex route to the first connected \chi\ge 3 family already fails at the selector layer. But [[selector-quotient-is-not-a-submodular-minor-of-connected-family.md]] shows that this selector obstruction is quotient-level, not minor-level: it does not descend automatically to a nonexpressibility theorem for the full family. And [[branch-min-route-for-connected-family-fails-at-local-submodularity.md]] shows that a different exact factorization,

\[ \lambda_M(L)=\min\bigl(U(L),\,1+S(L)\bigr), \]

also fails in its obvious local-gadget implementation.

This is a derived structural obstruction statement.

  1. By [[multiple-parallel-classes-on-one-circuit-give-connected-cut-rank-at-least-three-family.md]],

    \[ \lambda_M(L) = \sum_{i=1}^t \mathbf 1[0<p_i(L)<|P_i|] + \varepsilon_L\,\mathbf 1[\exists i:\ p_i(L)=0] + (1-\varepsilon_L)\,\mathbf 1[\exists i:\ p_i(L)=|P_i|]. \]

    Renaming the three indicator blocks gives the displayed decomposition.

  2. Thus the connected family already separates cleanly into old local pieces M_i and one new global interface gadget g(u,C,D).

  3. By [[selected-or-selector-is-not-hidden-vertex-graph-cut-expressible.md]], the selector g(u,C,D)=(1-u)C+uD is not in the binary submodular expressive class \langle\Gamma_{\mathrm{sub},2}\rangle.

  4. Therefore any hidden-vertex realization of the full connected family cannot factor only through the independent split indicators M_i and the compressed ternary interface (u,C,D).

Consequences for the current frontier:

  • the new connected family is not blocked by low-order decomposition anymore, but it is also not captured by the old threshold-lift gadget stack;
  • the first unsolved connected \chi\ge 3 regime has now been reduced to one concrete selector bottleneck plus one remaining lift problem;
  • this is not yet a nonrepresentability theorem for the whole family, because the family might still admit a more global construction bypassing this compressed-state route, and the selector quotient is not a closure-preserving minor of the full family.

Dependencies

  • [[multiple-parallel-classes-on-one-circuit-give-connected-cut-rank-at-least-three-family.md]]
  • [[selected-or-selector-is-not-hidden-vertex-graph-cut-expressible.md]]
  • [[selector-quotient-is-not-a-submodular-minor-of-connected-family.md]]
  • [[branch-min-route-for-connected-family-fails-at-local-submodularity.md]]

Conflicts/Gaps

  • This node does not prove that the connected multi-parallel-circuit family fails ordinary hidden-vertex graph-cut representability.
  • It proves only that the natural compressed-state route reduces to the selector g, and that this selector is itself not hidden-vertex graph-cut expressible.
  • The possibility of a more global non-compressed construction remains open, [[selector-quotient-is-not-a-submodular-minor-of-connected-family.md]] explains why the selector obstruction does not lift automatically by standard closure operations, and [[branch-min-route-for-connected-family-fails-at-local-submodularity.md]] explains why the alternative one-branch-bit local factorization also fails.
  • Even a positive realization theorem for this family would still not by itself yield routing-style CD(T_n,G) semantics on the physical qubit set.

Sources

  • 10.1016/j.dam.2009.07.001
  • Kashyap 2008 preprint: A Decomposition Theory for Binary Linear Codes