Convex-Hull Decomposition for Mixed-Integer Bipartite Systems

Duplicate subtree-hull record: a gluing attempt and its distributional gap

Definitions and mathematical statement

Shared notation.

Standard number systems are $\mathbb N,\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$. Specialized notation and index ranges follow the cited source and the definitions below.

For a subtree $T$, its constraints and integral coordinates are restricted from the graph. The conjectured equality compares the convex hull of all mixed-integer solutions with the simultaneous convex-hull restrictions from the specified subtrees.

Record scope and qualifications.

The catalogue title is retained as metadata. Named certificates, contracts, bounds or frameworks in that title are not asserted as results of the original source extract. The supplied registry flags this extraction as unrecoverable. It is displayed as a literal source fragment; the definitions provide context rather than a replacement formal statement.

Source-record limitation: Source flags the statement as unrecoverable: The official report confirms that this repeats the same Conjecture 2 extracted as OWR-2489-004. No separate clean statement is promoted; the original record remains publicly visible for provenance.

Related catalogue records: 30001100. Separate source IDs are preserved for their provenance. The source text below is rendered literally where necessary; damaged formulas and composite extracts are not silently repaired into a new mathematical claim. The supplied catalogue marks this record as unrecoverable. Its extract and terminology are documented, but a complete original problem has not been reconstructed.

Statement recorded in the supplied source.

With S(G,I) as defined in the report and T the subtrees of G whose integral vertices are exactly the leaves, is the convex-hull identity conv(S(G,I))=

\textbackslash{}

bigcap_{T}conv$S(T,I\_T)$ valid for every denominator parameter k? It is known for k=2 and remains open for every k

\textbackslash{}

geq3. [S2]

Source status.

The supplied catalogue labels this source record open; that metadata was checked against the supplied snapshot on 2026-10-11. The label is preserved for provenance and is not an independent verification of present open status or mathematical correctness. The catalogue literature assessment is dated 2026-08-21.

Short English statement

The supplied fragment concerns subtree Decomposition of Mixed-Integer Convex Hulls. Its complete mathematical target is not recovered.

Sources

• S1 Ulam AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 30001103 (OWR-2489-009). Catalogue curation and metadata: CC BY 4.0. The source extract is retained; definitions, English summaries and qualifications are editorial additions. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Combinatorial Optimization $2009$, Oberwolfach Reports, DOI 10.4171/owr/2008/51, pp. 2875--2942 https://doi.org/10.4171/owr/2008/51.
• S3 network formulations https://doi.org/10.1287/moor.1080.0354.
• Source-specific Oberwolfach Reports licences, including CC BY-SA 4.0 where applicable, are retained; see THIRD_PARTY_NOTICES.md.

Verbatim supplied catalogue question

With S(G,I) as defined in the report and T the subtrees of G whose integral vertices are exactly the leaves, is the convex-hull identity conv(S(G,I))=

\textbackslash{}

bigcap_{T}conv$S(T,I\_T)$ valid for every denominator parameter k? It is known for k=2 and remains open for every k

\textbackslash{}

geq3.

Preserved duplicate and source scope

The supplied record is flagged unrecoverable because it repeats the same Conforti Conjecture 2 as record 30001100, rather than defining a second independent problem. Inspection of the primary report confirms the shared subtree identity. The denominator $k$ is the least positive integer making all rational edge right-hand sides integral. This manuscript retains the flag and original fragment and investigates a gluing proof of that shared question. It makes no claim to reconstruct a different missing theorem.

The literal ambient-domain omission persists.

On a single edge $uv$ with $I=\{u\}$ and $b_{uv}=1/3$, the edge-tree has two leaves but only one integral vertex, so it is excluded from the specified family. Any included singleton subtree has hull equal to its whole coordinate line, since both $\operatorname{conv}(\mathbb Z)$ and $\mathbb R$ equal $\mathbb R$. Thus the lifted subtree intersection imposes no constraint, while the global hull satisfies $x_u+x_v\ge1/3$. This also happens at denominator two, contradicting the source's stated known case if all hulls are interpreted in unrestricted ambient space. An implicit continuous relaxation or different subtree convention is therefore missing. This diagnostic is not treated as a resolution of the intended conjecture. All subsequent gluing observations concern the proposed proof mechanism, not a silent repair of the original statement.

Attempt to glue convex decompositions

Membership of $\bar x_T$ in a subtree hull supplies a finite distribution on feasible local points whose coordinate mean is $\bar x_T$. A tempting proof would glue these local distributions into a globally feasible random point with mean $\bar x$. Means on common coordinates are not enough to justify that step.

A precise gluing lemma under a stronger hypothesis.

Let finite distributions $P_A,P_B$ on coordinates indexed by $A,B$ agree as entire marginal distributions on $S=A\cap B$, with common marginal $\mu$. For consistent assignments $a,b$ having common restriction $s$ with $\mu(s)>0$, define \[ P(a,b)=\frac{P_A(a)P_B(b)}{\mu(s)}; \] put zero mass on all other pairs. Summing over compatible $b$ gives $P_A(a)\mu(s)/\mu(s)=P_A(a)$; if $\mu(s)=0$, every assignment restricting to $s$ has zero marginal mass, so nothing is lost. The same argument gives marginal $P_B$, and summing either marginal proves normalization. Every positive-mass global assignment has allowed local restrictions. Hence a gluing is possible with those full marginal hypotheses. The same construction can be iterated along a tree of variable blocks when, at each attachment, the intersection with all earlier blocks is the specified separator and its full marginal agrees. This follows by induction using the two-block argument, which preserves the already constructed marginal exactly.

Equal first moments do not imply compatible local laws.

A single coordinate with law supported equally on $\{-1,1\}$ has the same mean zero as the point mass at zero, but these distributions cannot be the two marginals of one shared coordinate. Thus even two local convex-combination witnesses cannot simply be combined from their means. Moreover cycle consistency can fail despite agreement of all singleton marginals. On four binary variables consider the relations \[ x_1=x_2,\quad x_2=x_3,\quad x_3=x_4,\quad x_4=1-x_1. \] Each individual relation admits a distribution on its two allowed pairs with each coordinate fair. More strongly, every forest obtained by deleting at least one cycle edge admits two complementary assignments on each component: choose a root bit and propagate equality or complementation along the unique paths. Fairly averaging complementary assignments gives mean $(1/2,1/2,1/2,1/2)$ on every such forest. Yet no global assignment exists, since the first three equalities imply $x_4=x_1$, contradicting the last relation. The incidence graph is an even cycle, so bipartiteness alone cannot make this generic gluing inference valid. These relations are not the source's one-sided covering inequalities; this is explicitly a counterexample to a general proof principle, not to the intended mixed-integer covering conjecture.

Adversarial audit and gap

Global feasible points always restrict to locally feasible points, and their finite convex combinations do too, proving the easy global-to-local inclusion. The reverse needs a structural argument producing compatible distributions, or another way to use the covering inequalities; the gluing lemma does not supply that compatibility from means. The audit separated full distributions from first moments, acyclic attachment from cycle consistency, and the generic binary counterexample from the exact source class. The duplicate status and literal-domain defect remain visible. No computation was performed and no independent target or new result is counted from this duplicate record.

Process and contributions

Mathematics and model-assisted adversarial self-audit: OpenAI gpt-6-astra, ultra reasoning, as dispatched for this research batch; exact serving revision not exposed. Codex (GPT-6; exact serving revision not exposed) materially assisted with orchestration and format review. No human mathematical authorship, mathematical edits, or independent human proof checking is asserted. Contribution prompt A was applied to the full definition and supplied source row, then prompt B was applied adversarially to the derived results. The item-specific audit above records the scope checks and rejected extrapolations. Local assembly and structural checks do not establish mathematical correctness. The source catalogue status is preserved in TOP_PROBLEM and is separate from this attempt status.

Integration review.

Codex (GPT-6; exact serving revision not exposed) reviewed the written arguments and expanded layout and source-reference wrappers. Repository metadata and the production web renderer were checked using Python 3.13 and JavaScript with MathJax 3.2.2. This model-assisted review is not independent human proof verification; no PDF compilation or formal proof checking is asserted.

Completion Estimate

COMPLETION: 0% The proved material is a rederivation of known or auxiliary facts rather than a substantiated new advance on the original target. The shared intended conjecture remains unresolved: local hull memberships provide means, not the compatible full marginal distributions needed by the gluing construction; the source fragment also omits an ambient convention.

References

The complete original Sources subsection above is retained, including catalogue attribution and licence notices. The additional list records primary sources actually consulted for this attempt on 11 October 2026; uncited source links reproduced above were not all rechecked.

• Oberwolfach Report 51/2008: Conforti, Combinatorial Mixed-Integer Programming, printed pp.2904--2905; Alcuin-number contribution, pp.2891--2893. Each relevant original passage read from cached primary PDF text on 11 October 2026. https://ems.press/content/serial-article-files/46195.

Final status

Unresolved in this attempt. The shared intended conjecture remains unresolved: local hull memberships provide means, not the compatible full marginal distributions needed by the gluing construction; the source fragment also omits an ambient convention.

Subtree-hull attempt: the ambient-relaxation omission and an integral boundary case

Definitions and mathematical statement

Shared notation.

Standard number systems are denoted by $\mathbb N,\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$; index ranges, computational models and specialized notation follow the cited problem source and the definitions below.

For a subtree $T$, its constraints and integral coordinates are restricted from the graph. The conjectured equality compares the convex hull of all mixed-integer solutions with the simultaneous convex-hull restrictions from the specified subtrees.

An integer program imposes integral coordinates on a system of constraints. A mixed-integer program allows both integral and real coordinates; $\operatorname{conv}(S)$ denotes the set of finite convex combinations of feasible points of $S$.

Statement recorded in the supplied source.

Let $G$ be bipartite, let $I$ be the set of integral-coordinate vertices, and let $S(G,I)=\{x:x_i+x_j\geq b_{ij}\text{ for }ij\in E,\ x_i\in\mathbb{Z}\text{ for }i\in I\}$. If $T$ ranges over subtrees of $G$ for which $I_T=V(T)\cap I$ is the set of leaves, is $\operatorname{conv}(S(G,I))=\bigcap_T\operatorname{conv}(S(T,I_T))$? The conjecture is known for denominator parameter $k=2$ and open for $k\geq3$. [S2]

Scope qualification.

The denominator parameter $k$ is not defined in the supplied question; its arithmetic assumptions are those of the report.

Source status.

The supplied catalogue labels this record open. Its source-status metadata was checked against the supplied snapshot on 2026-10-11. This import does not independently establish current open status or mathematical correctness. The catalogue literature assessment is dated 2026-08-21.

Short English statement

Determine whether all the stated leaf-integral subtree constraints describe the full mixed-integer convex hull.

Sources

• S1 Ulam AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 30001100 (OWR-2489-004). Catalogue curation and metadata: CC BY 4.0. The supplied source question is retained; definitions and the English summary are editorial additions. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Combinatorial Optimization $2009$, Oberwolfach Reports, DOI 10.4171/owr/2008/51, pp. 2875--2942 https://doi.org/10.4171/owr/2008/51.
• S3 current single-source flow results https://doi.org/10.1007/s10107-026-02365-x.
• S4 Salazar--Skutella https://doi.org/10.1016/S0167637709000133. Underlying Oberwolfach Reports material retains its source-specific licence, including CC BY-SA 4.0 where applicable; see THIRD_PARTY_NOTICES.md.

Verbatim supplied catalogue question

Let $G$ be bipartite, let $I$ be the set of integral-coordinate vertices, and let $S(G,I)=\{x:x_i+x_j\geq b_{ij}\text{ for }ij\in E,\ x_i\in\mathbb{Z}\text{ for }i\in I\}$. If $T$ ranges over subtrees of $G$ for which $I_T=V(T)\cap I$ is the set of leaves, is $\operatorname{conv}(S(G,I))=\bigcap_T\operatorname{conv}(S(T,I_T))$? The conjecture is known for denominator parameter $k=2$ and open for $k\geq3$.

Source recovery and literal-scope audit

The report defines $k$ as the least positive integer for which every $kb_{ij}$ is integral, with rational right-hand sides. Its Conjecture 2 really prints the subtree intersection in the supplied record and reports it known for $k=2$. Subtree hulls live on fewer coordinates; throughout, interpret them as cylinders in the full coordinate space. Under that literal reading the displayed identity omits an essential ambient restriction. Let $G$ be one edge $uv$, $I=\{u\}$, and $b_{uv}=1/3$. The only subtree containing the edge has leaves $\{u,v\}$, which are not exactly its integral vertices. Thus it is not allowed. Singleton subtrees, if a leaf convention allows any of them, have no edge inequalities and convex hull equal to the whole one-dimensional line, whether their sole coordinate is integral or continuous. Consequently the displayed right-hand side is $\mathbb R^2$, including $(0,0)$, whereas every point of $\operatorname{conv}(S(G,I))$ satisfies $x_u+x_v\ge1/3$. The same argument with $b_{uv}=1/2$ conflicts with the source's own known-$k=2$ remark. This is evidence of a missing ambient-domain convention, not a new disproof of the intended research conjecture. We do not silently repair the original definition or claim a full solution from that omission.

The easy inclusion survives every such convention.

For each allowed subtree $T$, restriction of any point of $S(G,I)$ lies in $S(T,I_T)$. Restriction is linear, so restricting a finite convex combination gives a convex combination of such subtree points. Therefore \[ \operatorname{conv}(S(G,I))\subseteq \bigcap_T\operatorname{conv}(S(T,I_T)). \] The unresolved mathematical direction is the reverse, with whatever original ambient relaxation was intended. A generic appeal to convexity proves only the displayed easy inclusion.

A complete boundary case for the attempted rounding route

Suppose first that every coordinate is integral. Put $B_{uv}=\lceil b_{uv}\rceil$ and $Q=\{x:x_u+x_v\ge B_{uv}\text{ for }uv\in E\}$. We prove $Q=\operatorname{conv}(S(G,U\cup V))$ directly. For $x\in Q$, change signs on the second bipartition: $y_u=x_u$ for $u\in U$ and $y_v=-x_v$ for $v\in V$. Then $y_u-y_v\ge B_{uv}$, an integer right-hand side. For one common $\theta\in[0,1)$ set $z_i=\lfloor y_i+\theta\rfloor$. Since $y_u\ge y_v+B_{uv}$, monotonicity of the floor and its invariance under integer translation imply $z_u-z_v\ge B_{uv}$. Undo the sign change. The resulting vector is integral and feasible for all original edges simultaneously. Each rounded coordinate has expectation $y_i$ under uniform $\theta$: writing $y_i=m_i+r_i$, $0\le r_i<1$, its two values $m_i,m_i+1$ have probabilities $1-r_i,r_i$. There are finitely many threshold values $1-r_i$, so the rounded vectors have a finite distribution. Their weighted average is $x$, proving the nontrivial hull inclusion. The reverse follows because an integral sum at least $b_{uv}$ is at least $B_{uv}$ and inequalities persist under averaging.

In this all-integral case, every single edge is an admissible subtree and its hull is its rounded half-space by the same two-vertex proof. Their intersection is $Q$. Every larger admissible subtree imposes valid restrictions on the global hull, so the subtree intersection equals $Q$. This verifies a special case for arbitrary rational denominators, but it is standard bipartite integral rounding, not progress for the mixed case. If all $b_{uv}$ are integral, the same rounding also shows that the continuous relaxation is the hull for every choice of $I$: it expresses any relaxed point as an average of fully integral feasible points, which are in particular feasible for the prescribed subset $I$.

Why the general rounding attempt fails and what is left

For a fractional right-hand side the common-floor proof cannot use $\lfloor a+B\rfloor=\lfloor a\rfloor+B$, since $B$ is no longer integral. Already on one edge with $x_u=x_v=1/4$ and $b_{uv}=1/2$, the sign-changed coordinates are $1/4,-1/4$. For $1/4\le\theta<3/4$, both floors are zero, yielding a rounded sum zero that violates the edge inequality. Rounding only the designated integral vertices requires a correlated adjustment of continuous neighbors; doing it independently does not inherit the integer-difference argument. The source's finer subtree facets are precisely the kind of information this crude rounding ignores. The audit distinguished the literal omitted-relaxation diagnostic from the intended mixed-integer conjecture, handled singleton-leaf conventions, and used finite convex combinations rather than an unexamined closure operation. No computation was performed. The intended general denominator case remains unresolved, and the source omission is not assigned mathematical progress credit.

Process and contributions

Mathematics and model-assisted adversarial self-audit: OpenAI gpt-6-astra, ultra reasoning, as dispatched for this research batch; exact serving revision not exposed. Codex (GPT-6; exact serving revision not exposed) materially assisted with orchestration and format review. No human mathematical authorship, mathematical edits, or independent human proof checking is asserted. Contribution prompt A was applied to the full definition and supplied source row, then prompt B was applied adversarially to the derived results. The item-specific audit above records the scope checks and rejected extrapolations. Local assembly and structural checks do not establish mathematical correctness. The source catalogue status is preserved in TOP_PROBLEM and is separate from this attempt status.

Integration review.

Codex (GPT-6; exact serving revision not exposed) reviewed the written arguments and expanded layout and source-reference wrappers. Repository metadata and the production web renderer were checked using Python 3.13 and JavaScript with MathJax 3.2.2. This model-assisted review is not independent human proof verification; no PDF compilation or formal proof checking is asserted.

Completion Estimate

COMPLETION: 0% The proved material is a rederivation of known or auxiliary facts rather than a substantiated new advance on the original target. The literal intersection lacks ambient constraints; after acknowledging that defect, no reverse inclusion for the intended general mixed-integer conjecture is proved.

References

The complete original Sources subsection above is retained, including catalogue attribution and licence notices. The additional list records primary sources actually consulted for this attempt on 11 October 2026; uncited source links reproduced above were not all rechecked.

• Oberwolfach Report 51/2008: Conforti, Combinatorial Mixed-Integer Programming, printed pp.2904--2905; Alcuin-number contribution, pp.2891--2893. Each relevant original passage read from cached primary PDF text on 11 October 2026. https://ems.press/content/serial-article-files/46195.

Final status

Unresolved in this attempt. The literal intersection lacks ambient constraints; after acknowledging that defect, no reverse inclusion for the intended general mixed-integer conjecture is proved.