Direct Sums Of Threshold-Lift Pieces Stay Hidden-Vertex Representable¶

Claim/Theorem¶

Let M_1,\dots,M_t be binary matroids on pairwise disjoint ground sets E_1,\dots,E_t, and assume each M_i lies in the circuit-plus-parallel-class threshold-lift class of [[parallel-extension-of-binary-circuit-gives-threshold-lift-cut-rank.md]]. Let

\[ M:=M_1\oplus \cdots \oplus M_t \]

be their direct sum on E=E_1\sqcup\cdots\sqcup E_t.

Then the connectivity function of M is

\[ \lambda_M(L)=\sum_{i=1}^t \lambda_{M_i}(L\cap E_i) \]

for every cut L\subseteq E. Consequently, if H is any full-row-rank binary matrix whose column matroid is M, then

\[ \chi_L(\mathcal S_H)=\sum_{i=1}^t \chi_{L\cap E_i}(\mathcal S_{H_i}), \]

and \chi_L(\mathcal S_H) is ordinarily hidden-vertex graph-cut representable.

More concretely, if E_i is partitioned as P_i\sqcup Q_i with

\[ \chi_{L\cap E_i} = \mathbf 1[p_i(L)\ge 1,\ q_i(L)<s_i] + \mathbf 1[q_i(L)\ge 1,\ p_i(L)<m_i], \]

then the direct sum has cut-rank function

\[ \chi_L(\mathcal S_H) = \sum_{i=1}^t \Bigl( \mathbf 1[p_i(L)\ge 1,\ q_i(L)<s_i] + \mathbf 1[q_i(L)\ge 1,\ p_i(L)<m_i] \Bigr), \]

and is realized by the sum of the corresponding four-hidden-bit threshold-lift energies on disjoint hidden-variable sets.

This gives a genuinely broader positive class than the single circuit-plus-parallel-class theorem: a nontrivial direct sum of two such pieces is disconnected and therefore cannot itself be a single circuit-plus-parallel-class matroid.

This is a derived structural theorem.

By [[cross-cut-stabilizer-rank-rank-formula.md]], stabilizer cut rank equals binary-matroid connectivity, so it is enough to work with \lambda_M.
For a direct sum of matroids, ranks add:

\[ r_M(L)=\sum_{i=1}^t r_{M_i}(L\cap E_i), \qquad r(M)=\sum_{i=1}^t r(M_i). \]

Hence

\[ \lambda_M(L) = r_M(L)+r_M(E\setminus L)-r(M) = \sum_{i=1}^t \lambda_{M_i}(L\cap E_i). \]

Each M_i is in the threshold-lift class, so by [[parallel-extension-of-binary-circuit-gives-threshold-lift-cut-rank.md]] and [[parallel-class-affine-basis-family-is-hidden-vertex-graph-cut-representable.md]] there is a binary-submodular realizing energy

\[ E_i(x_{E_i},a_i,b_i,c_i,d_i) \]

with four hidden bits such that

\[ \lambda_{M_i}(L\cap E_i)=\min_{a_i,b_i,c_i,d_i} E_i. \]

Summing these energies on disjoint hidden-variable sets gives

\[ E:=\sum_{i=1}^t E_i. \]

Since binary submodularity is preserved under addition, E is again a binary submodular polynomial, and minimizing over all hidden bits yields exactly \lambda_M(L). 5. If at least two summands are nontrivial, then M is disconnected, while every single circuit-plus-parallel-class piece has connected simplification on P_i\cup Q_i. So this is strictly broader than the one-piece structural class.

Consequences for the current frontier:

the threshold-lift route does extend beyond a single circuit-plus-parallel-class piece;
the extension currently justified on disk is by direct sums, i.e. 1-sums or disconnected assemblies of threshold-lift components;
this does not yet justify closure under 2-sums or 3-sums;
existing nodes [[exact-2-separation-is-2-sum.md]] and [[nonminimal-exact-3-separation-is-3-sum.md]] show that those low-order gluing operations are exactly the constant-connectivity \chi=1 and \chi=2 regimes, so by themselves they point toward small separators rather than the large balanced-cut rank needed for compiler-native routing lower bounds.

Dependencies¶

[[cross-cut-stabilizer-rank-rank-formula.md]]
[[parallel-extension-of-binary-circuit-gives-threshold-lift-cut-rank.md]]
[[parallel-class-affine-basis-family-is-hidden-vertex-graph-cut-representable.md]]
[[exact-2-separation-is-2-sum.md]]
[[nonminimal-exact-3-separation-is-3-sum.md]]

Conflicts/Gaps¶

This node proves closure only under direct sums, not under 2-sums, 3-sums, or more general matroid gluing operations.
The theorem is derived from rank additivity and the existing explicit threshold-lift gadgets; it is not stated verbatim in the cited papers.
Direct-sum closure enlarges hidden-vertex representability but does not help the routing frontier by itself, because disconnected or low-order-glued objects remain compatible with small separator structure.

Sources¶

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