Facet Preservation in Recursive Hoffman-Cut Decompositions

Definitions and mathematical statement

A valid inequality $a^\mathsf T x\ge b$ for a nonempty polyhedron $P$ defines a facet when its equality face \[ F=\{x\in P:a^\mathsf T x=b\} \] is nonempty and has $\dim F=\dim P-1$, with dimension taken in the affine hull of $P$.

The source conjecture is: "In the recursive decomposition of a non-facet Hoffman cut into Hoffman cuts on smaller node sets, every resulting cut should already define a facet." In the notation of the intended source construction, if a non-facet cut $H_S$ associated with a node set $S$ is decomposed into cuts \[ H_{S_j}:a_j^\mathsf T x\ge b_j,\qquad S_j\subsetneq S, \] the requested facet conclusion for each resulting component is \[ \dim\{x\in P_j:a_j^\mathsf T x=b_j\}=\dim P_j-1, \] where $P_j$ must be the precise polyhedron relative to which that component is asserted to be a facet in the report. This notation only exposes the content of the conjecture; it does not supply a new decomposition rule.

The excerpt does not give the network/capacity data, the polyhedron being described, the formula for its Hoffman cuts, or the recursive splitting criterion. It also does not say whether facetness is relative to an induced smaller-node polyhedron or a common original polyhedron, or whether "every resulting cut" means immediate components or only terminal components. Those distinctions affect the mathematical assertion. Consequently the quoted source claim is preserved, but a completely quantified theorem cannot be recovered from this record alone by substituting a generic flow-polyhedron model.

The literature assessment checked on 21 August 2026 says the report presents the claim as a conjecture, while the extracted search found no authoritative later proof or counterexample. It explicitly recommends treating its status as unverified rather than concluding that it remains open solely from the historical report. The registry's open label does not override that qualification.

Short English statement

The conjecture says that decomposing a non-facet Hoffman cut into smaller-node Hoffman cuts already produces facets. The exact network polyhedron and decomposition rule are missing, so the source claim is retained with those unresolved formulation details.

Sources

• Mathematics in the Supply Chain (2005), Oberwolfach Reports, DOI 10.4171/owr/2004/19, pp. 963--1036, https://doi.org/10.4171/owr/2004/19. The supplied proposed year is 2004; the citation year is reproduced as given.
• "OWR report," supplied literature source for the assessment checked 21 August 2026, https://oa.tib.eu/renate/server/api/core/bitstreams/361c45b4-a7f7-46eb-8d08-cedf09127b4a/content. The assessment supplies no authoritative later proof or counterexample.
• Local UnsolvedMath registry, permanent ID $30000008$, exact source code catalogue entry, created 25 August 2026 and updated 16 September 2026. Statement status is exact; its dated literature triage explicitly leaves current status unverified.