Odd Two-Element Multi-Parallel Family Violates Terminal Hypergraph Cut Condition¶

Claim/Theorem¶

Keep the notation of [[multiple-parallel-classes-on-one-circuit-give-connected-cut-rank-at-least-three-family.md]], [[two-element-multi-parallel-circuit-family-satisfies-direct-fsep.md]], and [[simple-binary-connectivity-violates-nonnegative-hypergraph-cut-condition.md]].

There is an infinite connected post-threshold subfamily of the first multi-parallel-circuit boundary on which every exact terminal routing-style semantics already fails.

More precisely, let M_t be the size-2 multi-parallel-circuit family with ground set

\[ E=P_1\sqcup\cdots\sqcup P_t\sqcup\{u\}, \qquad |P_i|=2 \]

from [[two-element-multi-parallel-circuit-family-satisfies-direct-fsep.md]], and let

\[ f_t(x):=\lambda_{M_t}(L_x). \]

Assume t\ge 3 is odd. Then:

M_t is connected and reaches cut rank at least 3.
f_t is not the cut-capacity function of any undirected hypergraph with nonnegative terminal capacities.
Consequently no exact terminal graph-cut, packet-demand, path-routing, or terminal nonnegative-hypergraph semantics can represent this infinite connected odd-t subfamily on the physical terminals.

So the first connected \chi\ge 3 family beyond threshold-lift already contains an infinite connected terminal-side semantic impossibility subfamily.

Proof sketch:

By [[multiple-parallel-classes-on-one-circuit-give-connected-cut-rank-at-least-three-family.md]], the family is connected, and for t\ge 3 there are cuts of rank t\ge 3.
Let

\[ X:=P_1\cup\cdots\cup P_t. \]

Then |X|=2t, and every subset Y\subseteq X has u\notin Y.
For each class P_i=\{a_i,b_i\}, define

\[ s_i(Y):=\mathbf 1[|Y\cap P_i|=1], \qquad c_i(Y):=\mathbf 1[Y\cap P_i=P_i]. \]

Since u\notin Y, the connectivity formula from [[multiple-parallel-classes-on-one-circuit-give-connected-cut-rank-at-least-three-family.md]] becomes

\[ f_t(Y)=\sum_{i=1}^t s_i(Y)+\mathbf 1[\exists i:\ c_i(Y)=1]. \]
Let f^{(i)}(X) denote Yamaguchi's Möbius layer, as in [[simple-binary-connectivity-violates-nonnegative-hypergraph-cut-condition.md]].
Each local split indicator s_i depends only on the two bits in P_i, so its full Möbius coefficient on the larger set X vanishes by cancellation over the other 2t-2 coordinates. Therefore

\[ f_t^{(2t)}(X) = \Bigl(\mathbf 1[\exists i:\ c_i=1]\Bigr)^{(2t)}(X). \]
Expand the OR term by inclusion-exclusion:

\[ \mathbf 1[\exists i:\ c_i=1] = \sum_{\varnothing\ne I\subseteq[t]}(-1)^{|I|+1}\prod_{i\in I} c_i. \]

Since each c_i=x_{a_i}x_{b_i}, the coefficient of the full monomial

\[ \prod_{i=1}^t x_{a_i}x_{b_i} \]

is exactly the I=[t] coefficient, namely

\[ (-1)^{t+1}. \]

Hence

\[ f_t^{(2t)}(X)=(-1)^{t+1}. \]
Because t is odd, one gets

\[ f_t^{(2t)}(X)=1. \]

But 2t is even, so Yamaguchi's Theorem 3.3 requires every nonnegative terminal hypergraph cut function f to satisfy

\[ f^{(2t)}(X)\le 0. \]

This is violated.
Therefore f_t is not a nonnegative terminal hypergraph cut function. Since terminal graph cuts and packet/path routing semantics are special cases, they fail as well.

Consequences for the current frontier:

the multi-parallel boundary is no longer terminal-side open on its first infinite connected \chi\ge 3 subfamily;
survival of the direct F_{\mathrm{sep}} test does not rescue routing-style semantics;
the remaining gap on this boundary is now strictly about nonterminal auxiliary semantics, not terminal routing-style semantics.

Dependencies¶

[[multiple-parallel-classes-on-one-circuit-give-connected-cut-rank-at-least-three-family.md]]
[[two-element-multi-parallel-circuit-family-satisfies-direct-fsep.md]]
[[simple-binary-connectivity-violates-nonnegative-hypergraph-cut-condition.md]]

Conflicts/Gaps¶

This theorem rules out exact terminal nonnegative-hypergraph semantics on an infinite connected odd-t subfamily, but it does not decide hidden-vertex representability for that family.
It is proved here for the size-2 subfamily. It does not yet cover arbitrary class sizes in the full multi-parallel-circuit family.
It does not rule out nonterminal auxiliary constructions, signed capacities, or other algebraic semantics.

Sources¶

10.1016/j.disc.2016.02.010
10.48550/arXiv.2109.14599