Matroid Connectivity Does Not Force Hypergraph Approximation

Claim/Theorem

Let \(M\) be a matroid on ground set \(E\) with rank function \(r_M\), and let

\[ \lambda_M(A):=r_M(A)+r_M(E\setminus A)-r_M(E). \]

Then the current hypergraph-representation obstruction already survives at the full matroid-connectivity level.

More precisely:

1. Beideman, Chandrasekaran, Chekuri, and Xu define the symmetrization of a set function by

\[ f^{\mathrm{sym}}(A)=f(A)+f(E\setminus A)-f(E)-f(\varnothing). \]

For a matroid rank function \(r_M\), this is exactly the connectivity function:

\[ r_M^{\mathrm{sym}}(A)=\lambda_M(A). \]

1. Their Proposition 2 states: if the symmetrization of every matroid rank function were \alpha-hypergraph-approximable, then every rational-valued symmetric submodular function would be \alpha-hypergraph-approximable.
2. Their Theorem 3, sharpened internally to Theorem 11, states that for every sufficiently large n there exists a matroid rank function

\[ r:2^{[n]}\to \mathbb Z_{\ge 0} \]

such that its symmetrization \(r^{\mathrm{sym}}=\lambda_M\) is not \alpha-hypergraph-approximable for

\[ \alpha=o\!\left(\frac{n^{1/3}}{\log^2 n}\right). \]

1. On the positive side, the same paper proves that symmetrized rank functions of uniform and partition matroids are 64-hypergraph-approximable.

Therefore no theorem of the form

\[ \text{``every matroid connectivity function admits a constant-factor hypergraph-cut realization''} \]

can be true. Any positive realization theorem for stabilizer cut rank

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

must use structure beyond the bare fact that \(\chi_L(\mathcal S)\) is a matroid connectivity function. In particular, the remaining frontier is now specifically about the binary or stabilizer subclass, not about generic matroid connectivity.

This is a sharper obstruction than [[generic-submodular-demand-does-not-force-classical-routing-realization.md]]: the failure is not merely at the level of arbitrary symmetric submodular functions, but already at the level of symmetrized matroid rank.

Proof Sketch

1. [[cross-cut-stabilizer-rank-rank-formula.md]] identifies \(\chi_L(\mathcal S)\) with the connectivity function of the column matroid of any stabilizer matrix, so stabilizer cut rank lies inside the matroid-connectivity subclass.
2. Beideman et al., Proposition 2, reduce general symmetric-submodular hypergraph approximation to symmetrized matroid rank.
3. Beideman et al., Theorem 3 / Theorem 11, then show that some symmetrized matroid rank functions already fail o(n^{1/3}/\log^2 n)-approximation by hypergraph cut functions.
4. Hence generic matroid connectivity is still too broad a class for any constant-factor hypergraph representation theorem.
5. Their Theorem 5, together with Lemma 17 and Theorem 18, shows that special matroid families such as uniform and partition matroids do admit constant-factor hypergraph approximation.

So the live question is now:

• do binary matroid connectivity functions, hence stabilizer cut-rank functions, form a better-behaved subclass than arbitrary matroid connectivity functions,
• or does the Beideman obstruction persist even after restricting to binary matroids and stabilizer spaces?

Dependencies

• [[cross-cut-stabilizer-rank-rank-formula.md]]
• [[stabilizer-cut-rank-defines-canonical-submodular-cd-object.md]]
• [[generic-submodular-demand-does-not-force-classical-routing-realization.md]]

Conflicts/Gaps

• The hard matroid in Beideman et al. is existential; the paper does not identify it as binary or representable over GF(2).
• So this node does not yet produce a counterexample inside the stabilizer or binary-matroid subclass.
• The positive approximation results cover only special matroid families, not arbitrary binary matroids.
• This node concerns nonnegative hypergraph-cut approximation. It does not resolve the auxiliary-variable graph-cut route for binary matroid connectivity.

Sources

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