Skip to content

Smallest Connected Multi-Parallel-Circuit Member Has No 1-Or-2-Auxiliary Realization In Large Coefficient Box

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]], and write

\[ f_{2,2,2}(x):=\lambda_{M_{2,2,2}}(L_x), \qquad x\in\{0,1\}^7. \]

Fix k\in\{1,2\}. Consider quadratic pseudo-Boolean polynomials

\[ E(x,h) = c+\sum_i \alpha_i z_i+\sum_{i<j}\beta_{ij} z_i z_j, \]

where z=(x,h) ranges over the 7+k visible-plus-hidden bits, every quadratic coefficient satisfies

\[ \beta_{ij}\le 0, \]

and every coefficient lies in the box

\[ [-64,64]. \]

Then there is no such E with

\[ f_{2,2,2}(x)=\min_{h\in\{0,1\}^k} E(x,h) \qquad\text{for all }x\in\{0,1\}^7. \]

Equivalently: exhaustive exact MILP search rules out every hidden-vertex graph-cut realization of f_{2,2,2} with 1 or 2 auxiliary bits inside this large coefficient box.

This is a derived exact bounded-budget obstruction.

  1. By [[smallest-connected-multi-parallel-circuit-member-survives-all-four-ary-exact-minors.md]], the target function is the 7-ary cut-rank function of the smallest connected multi-parallel-circuit member.

  2. Any sum of binary submodular terms on the visible and hidden bits is exactly a quadratic pseudo-Boolean polynomial with all pairwise coefficients nonpositive, and minimizing over the hidden bits gives the usual hidden-vertex graph-cut expressive class.

  3. For fixed k, exact existence inside the coefficient box reduces to a mixed-integer linear feasibility problem. Introduce one binary selector

    \[ s_{x,h}\in\{0,1\} \]

    for each visible assignment x and hidden assignment h, with

    \[ \sum_h s_{x,h}=1 \]

    for each x.

  4. For every pair (x,h), impose the lower-bound constraint

    \[ E(x,h)\ge f_{2,2,2}(x). \]

    To force equality on the selected hidden state, use

    \[ E(x,h)\le f_{2,2,2}(x)+M(1-s_{x,h}). \]

  5. Because there are

    \[ m_k:=1+(7+k)+\binom{7+k}{2} \]

    monomials in a quadratic polynomial on 7+k bits, and every coefficient lies in [-64,64], every value E(x,h) lies in

    \[ [-64m_k,64m_k]. \]

    Hence the linearization is exact once

    \[ M_k:=64m_k+5 \]

    is chosen.

  6. For k=1, one has

    \[ m_1=37, \qquad M_1=2373. \]

    The resulting exact MILP has 37 continuous coefficient variables, 256 selector binaries, and

    \[ 128+2\cdot 128\cdot 2=640 \]

    linear constraints. HiGHS reports the model infeasible.

  7. For k=2, one has

    \[ m_2=46, \qquad M_2=2949. \]

    The resulting exact MILP has 46 continuous coefficient variables, 512 selector binaries, and

    \[ 128+2\cdot 128\cdot 4=1152 \]

    linear constraints. HiGHS again reports the model infeasible.

  8. Therefore no hidden-vertex graph-cut realization of f_{2,2,2} exists with 1 or 2 auxiliaries inside the coefficient box [-64,64].

Consequences for the current frontier:

  • the first connected \chi\ge 3 witness now resists not only the selector quotient route, the one-branch-bit local route, the exact 4-ary closure route, and the direct F_{\mathrm{sep}} route, but also a genuinely global exact quadratic-submodular search with 1 or 2 auxiliaries in a large coefficient box;
  • any successful explicit realization for M_{2,2,2} must already use at least 3 hidden bits or coefficients outside this low-complexity search window;
  • this still falls short of whole-family nonexpressibility and still does not decide whether M_{2,2,2} is representable with a larger auxiliary budget.

Dependencies

  • [[smallest-connected-multi-parallel-circuit-member-survives-all-four-ary-exact-minors.md]]
  • [[two-element-multi-parallel-circuit-family-satisfies-direct-fsep.md]]
  • [[multiple-parallel-classes-on-one-circuit-give-connected-cut-rank-at-least-three-family.md]]

Conflicts/Gaps

  • This node does not prove that f_{2,2,2} is not hidden-vertex graph-cut representable.
  • It proves only a bounded-budget obstruction: no realization exists with 1 or 2 auxiliaries inside the coefficient box [-64,64].
  • The cases of 3 or more auxiliaries remain open, and the whole size-2 family remains open.
  • Even a future explicit realization or nonexpressibility theorem for this connected family would still need a separate bridge to routing-style CD(T_n,G) semantics.

Sources

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