Skip to content

Monotone Count Decomposition Is Column Generation Not Single Flow

Claim/Theorem

The natural flow/cut attempt for the f_3 monotone count-decomposition does not reduce to one standard max-flow or min-cut instance. The exact formulation is a column-generation integer covering problem whose pricing subproblem is a min-weight closure problem.

In the current instance, each label \beta must choose one boundary-compatible upset of the 2,849,631-element lattice L_P. The row equations then require that, for every closure element U,

\[ \sum_\beta h_\beta(U)=|U|. \]

Thus the columns are the possible label-upsets, while the rows are the closure elements. Optimizing a single label against linear row penalties is a min-weight closure problem on L_P, but the full decomposition couples all 50 label-upsets through the rank-sum equations. No total-duality or integrality theorem is currently identified for this intersection of 50 order polytopes.

The full structural and obstruction scan gives:

  • cover relations in L_P: 24,177,188;
  • interval/Hall violations for f_3: none;
  • forced-propagation contradictions for f_3: none;
  • zero lower-slack elements: 65;
  • zero upper-slack elements: 65;
  • critical-subposet size: 123;
  • critical binary ILP status: Optimal;
  • critical fractional LP status: Optimal.

The same pipeline still rejects the six-qubit fan certificate by a forced-one-below-forced-zero contradiction and an infeasible critical ILP. This confirms that the finite test is certificate-sensitive rather than a hidden-vertex invariant, consistent with [[fan-cone-certificates-are-not-hidden-vertex-invariants.md]].

The constructive attempts also fail only in restricted subclasses:

  • independent rank-sized low-fill choices inside each generator interval have 1,224,532 cover monotonicity violations;
  • independent rank-sized high-fill choices have 782,916 cover monotonicity violations;
  • seven deterministic rank-greedy extensions all fail by predecessor_union_exceeds_rank, the earliest at rank 3 after 98 processed closure elements.

These failures do not prove infeasibility. They rule out the currently tested direct interval-fill and greedy extension classes, and they sharpen the next exact task to either a real column-generation/dual certificate or a stronger higher-arity generator theorem.

Dependencies

  • [[f3-count-decomposition-is-coordinate-zero-toggle-boundary.md]]
  • [[full-closure-hall-and-critical-ilp-do-not-refute-f3-operation-extension.md]]
  • [[fan-cone-certificates-are-not-hidden-vertex-invariants.md]]
  • [[strict-hamming-replacement-and-meet-join-decomposition-do-not-close-certificate-lift.md]]

Conflicts/Gaps

  • No Hall, Farkas, or unsatisfiable-core certificate is found for f_3.
  • The flow/cut formulation is exact only as column generation; no finite column basis or separation-complete dual family has been extracted.
  • The constructive failures are subclass failures, not a theorem excluding arbitrary monotone label functions.

Sources

  • 10.1016/j.dam.2009.07.001
  • 10.1007/s10878-017-0136-y
  • local computation: docs/project_QEM-QEC/tmp/certificates/monotone_count_decomposition_report.json
  • local computation: docs/project_QEM-QEC/tmp/certificates/full_rank_order_extension_report.json
  • local script: docs/project_QEM-QEC/tmp/scripts/route_d_monotone_count_decomposition.py
  • local script: docs/project_QEM-QEC/tmp/scripts/route_d_full_rank_order_extension.py