Skip to content

Multiple Parallel Classes On One Circuit Give Connected Cut-Rank-At-Least-Three Family

Claim/Theorem

Let M be a binary matroid on

\[ E=P_1\sqcup\cdots\sqcup P_t\sqcup\{u\}, \qquad t\ge 2, \]

where each P_i is a nonempty parallel class. Assume that in the simplification \operatorname{si}(M), if p_i is any representative of P_i, then

\[ \{p_1,\dots,p_t,u\} \]

is a circuit.

Write

\[ m_i:=|P_i|, \qquad p_i(L):=|L\cap P_i|, \qquad \varepsilon_L:=\mathbf 1[u\in L]. \]

Then the connectivity function of M is

\[ \lambda_M(L) = \sum_{i=1}^t \mathbf 1[0<p_i(L)<m_i] + \varepsilon_L\,\mathbf 1[\exists i:\ p_i(L)=0] + (1-\varepsilon_L)\,\mathbf 1[\exists i:\ p_i(L)=m_i]. \]

Equivalently, for any full-row-rank binary stabilizer matrix H whose column matroid is M,

\[ \chi_L(\mathcal S_H)=\lambda_M(L) \]

has exactly the same formula.

Consequently:

  1. M is connected;

  2. if t\ge 3 and every m_i\ge 2, then M has a cut of rank at least 3, for example

    \[ L=\{u\}\cup\{e_i:\ e_i\in P_i\ \text{chosen arbitrarily}\} \]

    gives

    \[ \lambda_M(L)=t; \]

  3. if moreover both sides of that cut have size at least 4 (for example t\ge 4 and every m_i\ge 2), then this yields a natural connected family with nonminimal cuts of rank at least 3.

So the first connected post-gluing regime beyond the present threshold-lift-plus-direct-sum class already appears inside a very simple binary-matroid or stabilizer family: parallel extension of several elements of one circuit, not just one.

This is a derived structural theorem.

  1. By [[cross-cut-stabilizer-rank-rank-formula.md]], it is enough to compute the matroid connectivity function \lambda_M.

  2. Choose representatives p_i\in P_i. Because \{p_1,\dots,p_t,u\} is a binary circuit, one may choose coordinates so that

    \[ p_i=e_i\quad (1\le i\le t), \qquad u=e_1+\cdots+e_t. \]

  3. For a subset L, let

    \[ S_L:=\{i:\ p_i(L)>0\}. \]

    If u\notin L, then L contains only parallel copies of the basis vectors indexed by S_L, so

    \[ r_M(L)=|S_L|. \]

    If u\in L, then u adds one extra dimension exactly when not all basis directions are already present, i.e.

    \[ r_M(L)=|S_L|+\mathbf 1[\exists i:\ p_i(L)=0]. \]

    So in all cases

    \[ r_M(L)=|S_L|+\varepsilon_L\,\mathbf 1[\exists i:\ p_i(L)=0]. \]

  4. Applying the same argument to the complement with

    \[ T_L:=\{i:\ p_i(L)<m_i\} \]

    gives

    \[ r_M(E\setminus L)=|T_L|+(1-\varepsilon_L)\,\mathbf 1[\exists i:\ p_i(L)=m_i]. \]

  5. Since r_M(E)=t,

    \[ \lambda_M(L)=r_M(L)+r_M(E\setminus L)-t. \]

    Also,

    \[ |S_L|+|T_L|-t = \sum_{i=1}^t \mathbf 1[0<p_i(L)<m_i]. \]

    Substituting proves the displayed formula.

  6. The simplification \operatorname{si}(M) is a circuit, hence connected, and replacing elements by parallel classes preserves connectedness. So M is connected.

  7. If t\ge 3 and every m_i\ge 2, choose one element from each P_i and put those together with u on one side. Then every class is split, no class is entirely absent from the u-side, and the formula gives

    \[ \lambda_M(L)=\sum_{i=1}^t 1=t. \]

Consequences for the current frontier:

  • this is the first natural connected binary-matroid or stabilizer family on the graph that already reaches the \chi\ge 3 regime;
  • it lies outside the current threshold-lift-plus-direct-sum theorem stack, because [[threshold-lift-plus-direct-sum-class-never-reaches-connectivity-three-core.md]] shows that class never reaches a connected \chi\ge 3 core at all;
  • the current graph therefore now isolates a concrete next test family for ordinary hidden-vertex graph-cut representability;
  • but no positive hidden-vertex theorem or negative hidden-vertex obstruction for this multi-parallel-circuit family is yet on disk.

Dependencies

  • [[cross-cut-stabilizer-rank-rank-formula.md]]
  • [[parallel-extension-of-binary-circuit-gives-threshold-lift-cut-rank.md]]
  • [[threshold-lift-plus-direct-sum-class-never-reaches-connectivity-three-core.md]]

Conflicts/Gaps

  • This node identifies and computes the first connected post-gluing family beyond the current positive class, but it does not decide ordinary hidden-vertex graph-cut representability for that family.
  • The family is connected and already reaches cut rank 3 and higher, but the node does not prove internal 4-connectedness or any asymptotically large-width statement.
  • Even a future positive hidden-vertex theorem for this family would still not by itself yield routing-style CD(T_n,G) semantics on the physical qubit set.

Sources

  • 10.48550/arXiv.2109.14599
  • Kashyap 2008 preprint: A Decomposition Theory for Binary Linear Codes