Even Threshold-Lift Connected Family Separates Hidden-Vertex From Terminal Routing Semantics¶

Claim/Theorem¶

Keep the notation of [[parallel-class-affine-basis-family-is-hidden-vertex-graph-cut-representable.md]], [[parallel-extension-of-binary-circuit-gives-threshold-lift-cut-rank.md]], [[connected-hidden-vertex-realizability-still-fails-terminal-routing-semantics.md]], and [[simple-binary-connectivity-violates-nonnegative-hypergraph-cut-condition.md]].

There is an infinite connected binary-matroid or stabilizer family for which exact hidden-vertex realizability holds while every exact terminal routing-style semantics fails.

More precisely, let M_{m,s} be the threshold-lift family from [[parallel-extension-of-binary-circuit-gives-threshold-lift-cut-rank.md]] with ground set

\[ E=P\sqcup Q, \qquad |P|=m, \qquad |Q|=s, \]

where P is a parallel class and Q\cup\{p\} is a circuit in the simplification for any representative p\in P. Assume

\[ m\ge 2 \text{ is even}, \qquad s\ge 2. \]

Then:

M_{m,s} is connected.
Its connectivity function is

\[ \lambda_{M_{m,s}}(L) = \mathbf 1[p_L\ge 1,\ q_L<s] + \mathbf 1[q_L\ge 1,\ p_L<m], \]

where

\[ p_L:=|L\cap P|, \qquad q_L:=|L\cap Q|. \]
By [[parallel-class-affine-basis-family-is-hidden-vertex-graph-cut-representable.md]], this whole family is exactly hidden-vertex graph-cut representable by a four-hidden-bit binary-submodular energy.
But \lambda_{M_{m,s}} 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 family on the physical terminal set.

Therefore the witness-level D2 separation already lifts to an infinite connected family:

exact hidden-vertex realizability does not imply any exact terminal routing-style semantics, even on an infinite connected binary/stabilizer subclass.

Proof sketch for the terminal-semantic obstruction:

By [[parallel-extension-of-binary-circuit-gives-threshold-lift-cut-rank.md]], for every L\subseteq E,

\[ \lambda_{M_{m,s}}(L) = \mathbf 1[p_L\ge 1] + \mathbf 1[q_L\ge 1] - \mathbf 1[p_L=m]\mathbf 1[q_L\ge 1] - \mathbf 1[p_L\ge 1]\mathbf 1[q_L=s]. \]
Fix one element q\in Q and set

\[ X:=P\cup\{q\}, \qquad |X|=m+1. \]

Since s\ge 2, every subset Y\subseteq X satisfies q_Y<s. Writing

\[ a:=|Y\cap P|, \qquad b:=|Y\cap\{q\}|\in\{0,1\}, \]

one gets

\[ \lambda_{M_{m,s}}(Y)=\mathbf 1[a\ge 1]+\mathbf 1[b=1\ \text{and}\ a<m]. \]
Let f^{(i)}(X) denote Yamaguchi's Möbius layer for normalized symmetric set functions. The first term \mathbf 1[a\ge 1] depends only on P, so its full Möbius coefficient on X=P\cup\{q\} vanishes by cancellation over the q-coordinate.
The second term contributes

\[ \sum_{a=0}^{m-1}\binom{m}{a}(-1)^{m-a} = -1, \]

hence

\[ \lambda_{M_{m,s}}^{(m+1)}(X)=-1. \]
Yamaguchi's Theorem 3.3 requires every nonnegative terminal hypergraph cut function f to satisfy

\[ (-1)^i f^{(i)}(X)\le 0 \]

for every i and every X with |X|=i.
Here i=m+1 is odd because m is even, so

\[ (-1)^{m+1}\lambda_{M_{m,s}}^{(m+1)}(X) = (-1)^{m+1}(-1) = 1 > 0, \]

violating the necessary condition.
Therefore \lambda_{M_{m,s}} is not a nonnegative terminal hypergraph cut function. Since terminal graph cuts and packet/path routing semantics are special cases, they also fail.

Dependencies¶

[[parallel-class-affine-basis-family-is-hidden-vertex-graph-cut-representable.md]]
[[parallel-extension-of-binary-circuit-gives-threshold-lift-cut-rank.md]]
[[connected-hidden-vertex-realizability-still-fails-terminal-routing-semantics.md]]
[[simple-binary-connectivity-violates-nonnegative-hypergraph-cut-condition.md]]

Conflicts/Gaps¶

This theorem is exact for an infinite connected threshold-lift subfamily, but it does not yet cover all hidden-vertex representable connected binary matroids.
The terminal impossibility is about exact terminal nonnegative-hypergraph semantics and their graph/packet/path special cases. It does not rule out nonterminal auxiliary constructions, signed capacities, or other algebraic semantics.
The proof uses the specific threshold-lift formula. It does not yet extend to the first connected \lambda\ge 3 multi-parallel-circuit family.

Sources¶

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