Skip to content

Branch-Min Route For Connected Family Fails At Local Submodularity

Claim/Theorem

Let M be a member of the connected multi-parallel-circuit family from [[multiple-parallel-classes-on-one-circuit-give-connected-cut-rank-at-least-three-family.md]], with ground set

\[ E=P_1\sqcup\cdots\sqcup P_t\sqcup\{u\}. \]

For a cut L\subseteq E, write

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

Define

\[ S(L):=\sum_{i=1}^t \mathbf 1[0<p_i(L)<m_i] \]

and

\[ U(L):=\sum_{i=1}^t \mathbf 1\bigl[(\varepsilon_L=0\wedge p_i(L)>0)\ \vee\ (\varepsilon_L=1\wedge p_i(L)<m_i)\bigr]. \]

Equivalently, U(L) counts the classes P_i that are not monochromatic with the same cut value as the singleton element u.

Then the connectivity function from [[multiple-parallel-classes-on-one-circuit-give-connected-cut-rank-at-least-three-family.md]] satisfies the exact branch formula

\[ \lambda_M(L)=\min\bigl(U(L),\,1+S(L)\bigr). \]

So there is a natural candidate hidden-vertex realization route using one global branch bit h and local per-class gadgets

\[ \psi_m(u,h,x_P) := \begin{cases} \mathbf 1[(u=0\wedge p\ge 1)\ \vee\ (u=1\wedge p<m)],& h=0,\\ \mathbf 1[0<p<m],& h=1, \end{cases} \]

where p=\sum_{e\in P} x_e and m=|P|, because then formally

\[ \lambda_M(L) = \min_{h\in\{0,1\}} \left( h+\sum_{i=1}^t \psi_{m_i}\!\bigl(\varepsilon_L,h,x_{P_i}\bigr) \right). \]

However, for every m\ge 2, the visible local gadget \psi_m is not submodular. Consequently, by [[minimizing-hidden-binary-submodular-energy-preserves-submodularity.md]], \psi_m is not hidden-vertex graph-cut expressible. Therefore this whole branch-min route cannot be implemented by independent per-class hidden-vertex gadgets controlled only by one global branch bit.

This is a derived obstruction statement.

  1. By [[multiple-parallel-classes-on-one-circuit-give-connected-cut-rank-at-least-three-family.md]],

    \[ \lambda_M(L) = S(L) + (1-\varepsilon_L)\,\mathbf 1[\exists i:\ p_i(L)=m_i] + \varepsilon_L\,\mathbf 1[\exists i:\ p_i(L)=0]. \]

  2. If \varepsilon_L=0, let

    \[ F(L):=\#\{i:\ p_i(L)=m_i\}. \]

    Then U(L)=S(L)+F(L), while

    \[ \lambda_M(L)=S(L)+\mathbf 1[F(L)\ge 1]. \]

    Hence

    \[ \lambda_M(L)=\min\bigl(S(L)+F(L),\,1+S(L)\bigr)=\min\bigl(U(L),\,1+S(L)\bigr). \]

  3. If \varepsilon_L=1, let

    \[ E(L):=\#\{i:\ p_i(L)=0\}. \]

    Then U(L)=S(L)+E(L), while

    \[ \lambda_M(L)=S(L)+\mathbf 1[E(L)\ge 1]. \]

    So again

    \[ \lambda_M(L)=\min\bigl(S(L)+E(L),\,1+S(L)\bigr)=\min\bigl(U(L),\,1+S(L)\bigr). \]

    This proves the branch formula.

  4. The displayed h-decomposition is just a rewriting of \min(U,1+S) into two branches: h=0 yields U, and h=1 yields 1+S.

  5. Now fix any m\ge 2, and let \mathbf 1^m denote the all-ones class assignment. Consider

    \[ \alpha:=(u,h,x_P)=(0,1,\mathbf 1^m), \qquad \beta:=(u,h,x_P)=(1,0,\mathbf 1^m). \]

    Then

    \[ \psi_m(\alpha)=0, \qquad \psi_m(\beta)=0, \]

    because the h=1 branch sees a full class and the h=0 branch with u=1 also sees a class monochromatic with u.

    But

    \[ \alpha\wedge\beta=(0,0,\mathbf 1^m), \qquad \alpha\vee\beta=(1,1,\mathbf 1^m), \]

    so

    \[ \psi_m(\alpha\wedge\beta)=1, \qquad \psi_m(\alpha\vee\beta)=0. \]

    Therefore

    \[ \psi_m(\alpha)+\psi_m(\beta)=0<1=\psi_m(\alpha\wedge\beta)+\psi_m(\alpha\vee\beta), \]

    which violates submodularity.

  6. By [[minimizing-hidden-binary-submodular-energy-preserves-submodularity.md]], every hidden-vertex binary-submodular realization has a submodular visible function. Since \psi_m is not submodular, it cannot be hidden-vertex graph-cut expressible.

  7. Hence the branch formula does not directly give a connected positive theorem: the obvious implementation with one global branch bit and independent local gadgets is impossible already at the visible local-gadget level.

Consequences for the current frontier:

  • the selector quotient is not the only natural route to the first connected \chi\ge 3 family, but this alternative branch-min route also fails in its obvious local-gadget form;
  • the failure is stronger than a bounded-auxiliary search obstruction: it is an exact visible non-submodularity obstruction for the required per-class branch gadget;
  • this still does not rule out a more global hidden-vertex realization of the whole family, because a successful construction could couple the classes in a way that does not factor through independent \psi_{m_i} blocks.

Dependencies

  • [[multiple-parallel-classes-on-one-circuit-give-connected-cut-rank-at-least-three-family.md]]
  • [[minimizing-hidden-binary-submodular-energy-preserves-submodularity.md]]

Conflicts/Gaps

  • This node does not prove that the connected multi-parallel-circuit family itself is not hidden-vertex graph-cut representable.
  • It rules out only the specific \lambda_M=\min(U,1+S) implementation that factors through one global branch bit and independent per-class visible gadgets \psi_{m_i}.
  • A more global hidden-vertex realization that keeps richer cross-class structure remains open.
  • Even a future whole-family positive or negative theorem would still need a separate argument to connect hidden-vertex realizability to routing-style CD(T_n,G) semantics.

Sources

  • 10.48550/arXiv.2109.14599
  • 10.1016/j.dam.2009.07.001
  • 10.1007/s10878-017-0136-y
  • Kashyap 2008 preprint: A Decomposition Theory for Binary Linear Codes