Skip to content

Smallest Connected Multi-Parallel-Circuit Member Survives All Four-Ary Exact Minors

Claim/Theorem

Let M_{2,2,2} be the smallest connected member of the family from [[multiple-parallel-classes-on-one-circuit-give-connected-cut-rank-at-least-three-family.md]], with ground set

\[ E=P_1\sqcup P_2\sqcup P_3\sqcup\{u\}, \qquad |P_1|=|P_2|=|P_3|=2. \]

Write f_{2,2,2}:\{0,1\}^7\to\mathbb R for the associated cut-rank function

\[ f_{2,2,2}(x):=\lambda_{M_{2,2,2}}(L_x). \]

Consider any 4-ary minor of f_{2,2,2} obtained as follows:

  1. choose any 4 visible coordinates out of the 7,

  2. for each remaining coordinate, either

    • fix it to 0,
    • fix it to 1, or
    • minimize over it.

Then every such 4-ary minor satisfies Živný-Cohen-Jeavons condition Sep from Definition 21 / Theorem 22, and hence every such minor lies in \langle\Gamma_{\mathrm{sub},2}\rangle.

Equivalently: no exact 4-ary obstruction obtainable from the standard expressive-power closure operations of pinning and minimization separates even the smallest connected multi-parallel-circuit member from hidden-vertex graph-cut representability.

This is a derived exact finite theorem.

  1. By [[multiple-parallel-classes-on-one-circuit-give-connected-cut-rank-at-least-three-family.md]], the function f_{2,2,2} is the 7-ary Boolean function determined by

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

  2. There are

    \[ \binom{7}{4}=35 \]

    choices of visible coordinate set.

  3. For each such choice, the three hidden coordinates have 3^3=27 status patterns in {0,1,\min}^3.

  4. Hence there are

    \[ 35\cdot 27 = 945 \]

    candidate 4-ary minors to test.

  5. For each minor, compute its Boolean polynomial coefficients by Möbius inversion.

  6. For each of the six ordered Sep inequalities from Theorem 22, check exact coefficient nonpositivity.

  7. All 945 minors satisfy all six Sep inequalities.

By Theorem 22, every one of these 4-ary minors is therefore expressible by binary submodular functions with auxiliary variables.

Consequences for the current frontier:

  • the first connected \chi\ge 3 regime now survives not only the selector-quotient and branch-min local-gadget tests, but also the entire exact arity-4 closure toolkit already on disk;
  • any whole-family nonexpressibility theorem for this connected regime must therefore use a genuinely higher-arity obstruction than the known exact 4-ary Sep characterization;
  • conversely, this still falls short of a positive theorem, because surviving all exact 4-ary minors does not imply hidden-vertex representability of the original 7-ary function.

Dependencies

  • [[multiple-parallel-classes-on-one-circuit-give-connected-cut-rank-at-least-three-family.md]]
  • [[four-qubit-stabilizer-cut-rank-is-hidden-vertex-graph-cut-representable.md]]

Conflicts/Gaps

  • This node does not prove that f_{2,2,2} is hidden-vertex graph-cut representable.
  • It proves only that the exact arity-4 Sep theorem cannot refute the smallest connected test member, even after all standard pinning and minimization reductions.
  • The argument is derived computation rather than a literature theorem stated verbatim.
  • The result still lives inside auxiliary-variable expressibility and does not address routing-style CD(T_n,G) semantics.

Sources

  • 10.1016/j.dam.2009.07.001
  • 10.48550/arXiv.2109.14599