Generic Submodular Demand Does Not Force Classical Routing Realization

Claim/Theorem

The canonical stabilizer demand

\[ \lambda_{\mathcal S}(L)=\chi_L(\mathcal S) \]

is strong enough to define a compiler-native cut lower bound, but symmetry and submodularity alone are not strong enough to force any classical routing-style realization by nonnegative graph, hypergraph, or packet objects.

More precisely:

1. Exact undirected hypergraph cut realization with arbitrary capacities is too permissive. Yamaguchi proves that every normalized symmetric set function \(f:2^V\to\mathbb R\) is the cut-capacity function of some undirected hypernetwork if and only if \(f(\varnothing)=0\). Hence every stabilizer demand \(\lambda_{\mathcal S}\) admits some exact undirected hypergraph cut realization once signed hyperedge capacities are allowed.
2. Exact realization by undirected hypergraphs with nonnegative capacities is strictly smaller than the class of symmetric submodular functions. Yamaguchi proves only necessary conditions for such realizations and gives a five-element counterexample satisfying those conditions but still having no nonnegative undirected hypergraph realization.
3. Approximate realization by hypergraph cut functions also fails in general: Beideman, Chandrasekaran, Chekuri, and Xu prove that there exist symmetric submodular functions on an \(n\)-element ground set that cannot be approximated within o(n^{1/3}/log^2 n) by any hypergraph cut function.
4. Auxiliary-variable graph cuts are also not automatic: Zivny and Jeavons prove that not all Boolean submodular functions can be expressed as sums of binary submodular functions over a larger set of variables, so generic submodularity does not imply reduction to an ordinary graph-cut or min-cut formalism even with hidden variables.

Therefore the remaining frontier for Conjecture 3 is not to keep searching for a realization theorem from symmetry plus submodularity alone. Generic theory already blocks that hope. Any successful path, packet, guest-graph, or nonnegative hypergraph realization of \(\lambda_{\mathcal S}\) must use extra structure specific to the stabilizer or binary-matroid connectivity subclass.

Proof sketch:

1. [[stabilizer-cut-rank-defines-canonical-submodular-cd-object.md]] shows that \(\lambda_{\mathcal S}\) is a normalized symmetric submodular function.
2. Yamaguchi, Theorem 3.1, gives exact undirected hypergraph cut realization for every normalized symmetric set function. So exact hypergraph realization exists, but only in a signed-capacity sense.
3. Yamaguchi, Theorem 3.3 and Remark 2, show that nonnegative undirected hypergraph realization is genuinely narrower than symmetric submodularity.
4. Beideman et al. show that even approximation by hypergraph cut functions can require polynomial distortion for general symmetric submodular functions.
5. Zivny and Jeavons show that generic submodular functions are not all graph-cut expressible even after introducing auxiliary variables.
6. Since classical routing lower bounds such as [[packet-routing-o-c-plus-d.md]] require nonnegative packet, path, or edge-load semantics, the signed exact hypergraph realization from Step 2 does not close the routing gap.

So the live question is now sharply narrowed:

• either prove that stabilizer cut-rank functions \(\lambda_{\mathcal S}\) belong to a much better-behaved representable subclass than generic symmetric submodular functions,
• or produce a stabilizer-space counterexample showing that even this binary-matroid subclass still resists all reasonable classical routing realizations.

Dependencies

• [[stabilizer-cut-rank-defines-canonical-submodular-cd-object.md]]
• [[submodular-cut-congestion-lower-bounds-swap-only-compiler-depth.md]]
• [[stabilizer-cut-rank-is-not-a-graph-cut-function.md]]
• [[packet-routing-o-c-plus-d.md]]

Conflicts/Gaps

• The negative approximation and graph-cut expressibility results are stated for general symmetric submodular or general Boolean submodular functions, not specifically for binary matroid connectivity functions.
• So this node does not yet rule out a classical realization theorem on the smaller stabilizer-demand subclass.
• The positive hypergraph realization theorem is existential and may use signed capacities. It does not provide a canonical realization or one with packet-routing semantics.
• The literature used here does not resolve whether graphs with auxiliary vertices can realize every binary matroid connectivity function up to constants.

Sources

• 10.1016/j.disc.2016.02.010
• 10.4230/LIPIcs.FSTTCS.2022.6
• 10.1016/j.dam.2009.07.001