Simple Binary Connectivity Violates Nonnegative Hypergraph Cut Condition¶

Claim/Theorem¶

Even inside the binary-matroid and stabilizer subclass, the intrinsic cut-rank connectivity function need not be the cut-capacity function of any undirected hypergraph with nonnegative capacities.

Consider the full-row-rank binary matrix

\[ H= \begin{bmatrix} 1&0&1&0&1\\ 0&1&1&0&0\\ 0&0&0&1&1 \end{bmatrix} \]

on qubit set Q={1,2,3,4,5}, and let \mathcal S be its row space, equivalently the Z-type stabilizer space generated by

\[ Z_1Z_3Z_5,\qquad Z_2Z_3,\qquad Z_4Z_5. \]

Let \chi be the intrinsic cut-rank function from [[cross-cut-stabilizer-rank-rank-formula.md]]:

\[ \chi_L(\mathcal S)=\operatorname{rank}(H_L)+\operatorname{rank}(H_{Q\setminus L})-\operatorname{rank}(H). \]

For the three-element set X={1,2,3}, one computes

\[ \chi_{\{1\}}=\chi_{\{2\}}=\chi_{\{3\}}=1, \]

\[ \chi_{\{1,2\}}=\chi_{\{1,3\}}=2,\qquad \chi_{\{2,3\}}=1, \]

and

\[ \chi_{\{1,2,3\}}=1. \]

Now define the Möbius layer used by Yamaguchi (his f(i)(X)) for a normalized symmetric set function f by

\[ f^{(i)}(X):=\sum_{Y\subseteq X}(-1)^{|X\setminus Y|}f(Y), \qquad |X|=i. \]

Applying this to f=\chi and X={1,2,3} gives

\[ \chi^{(3)}(\{1,2,3\}) = \chi_{\{1,2,3\}} -\chi_{\{1,2\}}-\chi_{\{1,3\}}-\chi_{\{2,3\}} +\chi_{\{1\}}+\chi_{\{2\}}+\chi_{\{3\}} -\chi_{\varnothing} = 1-2-2-1+1+1+1-0 = -1. \]

But Yamaguchi's Theorem 3.3 (p. 4) states that if a normalized symmetric set function f is realizable as the cut-capacity function of an undirected hypergraph with nonnegative capacities, then for every i and every X of size i,

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

For i=3, this requires f^{(3)}(X)\ge 0. Our explicit binary-matroid connectivity function violates this:

\[ \chi^{(3)}(\{1,2,3\})=-1<0. \]

Therefore \chi_L(\mathcal S) is not realizable as a nonnegative hypergraph cut-capacity function.

Consequences for the current compiler-native frontier:

exact global nonnegative-hypergraph packaging of binary-matroid connectivity already fails in a simple 5-qubit binary example;
exact packet/path models on the terminal set fail a fortiori, since ordinary graph cut functions are a special case of nonnegative hypergraph cut functions;
the only remaining classical routes are therefore strictly more specialized, such as auxiliary-vertex min-cut constructions or other nonlocal algebraic encodings.

This is a sharper obstruction than the pivot-class incidence nodes:

[[basis-robust-fundamental-graph-loads-must-be-pivot-invariant.md]],
[[local-incidence-lifts-of-fundamental-graphs-are-not-pivot-robust.md]],
[[pivot-class-best-incidence-load-still-overestimates-connectivity.md]].

Those rule out basis-dependent and incidence-local constructions from fundamental graphs. The present node shows that even an exact global nonnegative hypergraph semantics can already fail for a simple binary connectivity function itself.

Dependencies¶

[[cross-cut-stabilizer-rank-rank-formula.md]]
[[binary-matroid-connectivity-equals-fundamental-graph-cut-rank.md]]

Conflicts/Gaps¶

This rules out exact realization by nonnegative hypergraph cut capacity, and hence exact packet/path demand graphs on the terminal set.
It does not yet rule out auxiliary-vertex graph-cut models in the stronger network-representability sense, nor signed hypergraph capacities, nor other nonclassical global constructions.
The example is small and does not yet show impossibility for every reasonable approximate realization notion.

Sources¶

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