Balanced Signings in the Subtour Polytope

Repeated signing question: a tree-flow construction and a dense fractional test

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 an undirected graph let $\delta(S)$ be the edges with exactly one endpoint in $S$. In the source's subtour cut relaxation, $x_e\geq0$ and $x(\delta(S))\geq2$ for every nonempty proper $S\subset V$. For an even terminal set $T$, a balanced signing is $s:T\to\{-1,1\}$ with $\sum_{v\in T}s(v)=0$. A capacitated transshipment routes these supplies and demands using edge capacities $x_e$; its cut feasibility condition is $|\sum_{v\in S\cap T}s(v)|\leq x(\delta(S))$ for every $S\subseteq V$.

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 is a duplicate extraction of the balanced-signing question retained in OWR-8415356-021. No separate clean mathematical statement is supplied; this source ID preserves its provenance.

Related catalogue records: 30004910. 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.

But is the following true: Open question 1. For any x

\textbackslash{}

in P and for any T

\textbackslash{}

subseteq VPof even cardinality, does there exist a signing s : T

\textbackslash{}

to

\textbackslash{}{−1, +1\textbackslash{}}

(with s(T ) := v

\textbackslash{}

inT s(v) = 0) such that there exists a transshipment (flow) f in G with capacities

\textbackslash{}{ue : e \textbackslash{}in E\textbackslash{}}

and whose excess at vertex v is s(v) for v

\textbackslash{}

in T and 0 otherwise. Open problem: Signings in the subtour polytope Michel Goemans [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-22.

Short English statement

The supplied fragment concerns balanced Signings in the Subtour Polytope. Its complete mathematical target is not recovered.

Sources

• S1 Ulam AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 30004911 (OWR-8415356-022). 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 $2022$, Oberwolfach Reports, DOI 10.4171/owr/2021/53, pp. 2893--2954 https://doi.org/10.4171/owr/2021/53.
• S3 Polygon structure for near-minimum cuts https://pubsonline.informs.org/doi/10.1287/opre.2022.2338.
• Source-specific Oberwolfach Reports licences, including CC BY-SA 4.0 where applicable, are retained; see THIRD_PARTY_NOTICES.md.

Verbatim supplied catalogue question

But is the following true: Open question 1. For any x

\textbackslash{}

in P and for any T

\textbackslash{}

subseteq VPof even cardinality, does there exist a signing s : T

\textbackslash{}

to

\textbackslash{}{−1, +1\textbackslash{}}

(with s(T ) := v

\textbackslash{}

inT s(v) = 0) such that there exists a transshipment (flow) f in G with capacities

\textbackslash{}{ue : e \textbackslash{}in E\textbackslash{}}

and whose excess at vertex v is s(v) for v

\textbackslash{}

in T and 0 otherwise. Open problem: Signings in the subtour polytope Michel Goemans

Duplicate provenance and a different attempted route

This is the trailing duplicate of the signing question in 30004910. The original paragraph on printed page 2946 supplies the subtour capacities and even terminal set. Here we test a spanning-tree construction rather than denominator clearing. It works whenever the original capacities dominate a unit-capacity spanning tree, but a valid subtour point need not have such a tree.

Alternating a depth-first terminal order on a tree.

Let $H$ be a rooted spanning tree, and list the vertices in depth-first preorder, visiting each child subtree completely before the next. In this order every rooted subtree is a consecutive interval: induction on the recursive traversal proves this directly. Restrict the list to the even terminal set $T$ and assign alternating $+1,-1$ signs. The sum of all signs is zero, and the signed sum on any rooted subtree has magnitude at most one because its terminals remain a consecutive subsequence of the alternating list.

For an edge from child $v$ to its parent, send signed flow $s(T\cap V_v)$ in that direction, where $V_v$ is the child subtree. This has magnitude at most one. At a nonroot vertex the outgoing signed flow minus the incoming child flows is the subtree sum minus the sums of its child subtrees, exactly its own sign if it is a terminal and zero otherwise. At the root the same statement follows from the total signed sum being zero. Thus this flow has precisely the required divergences. If $x_e\ge1$ on every edge of $H$, it respects the original capacities, with zero flow on edges outside the tree. For a subtour point whose support itself is a tree, every edge even has capacity at least two by applying the cut inequality to a component after removing that edge; hence this special case is included.

The threshold-tree extension fails on a valid subtour point.

On $K_n$ with $n\ge4$, assign every edge capacity $x_e=2/(n-1)<1$. A cut with side size $s$ has capacity $2s(n-s)/(n-1)\ge2$: the identity $s(n-s)-(n-1)=(s-1)(n-s-1)\ge0$ proves this for $1\le s\le n-1$. Thus $x$ is a valid source subtour point, but no edge reaches capacity one, so no spanning tree of the required type exists. The preceding construction cannot be extended merely by choosing a better threshold tree.

The signing statement itself is nevertheless true on this example, as an explicit fractional flow shows. Choose any balanced signing on the given even $T$, and set $s_v=0$ off $T$. For each ordered pair of distinct vertices define $f_{uv}=(s_u-s_v)/n$, with $f_{vu}=-f_{uv}$. The divergence at $u$ is \[ \sum_{v\ne u}f_{uv} =\frac{(n-1)s_u-\sum_{v\ne u}s_v}{n}=s_u, \] because the total sign sum is zero. Also $|f_{uv}|\le2/n\le2/(n-1)=x_{uv}$. Hence this is a valid transshipment within the original capacities. Failure of the tree certificate is therefore not a counterexample to the original signing question.

First gap and audit

The source paragraph and its thin-tree motivation were inspected. The tree construction gives a rigorous sufficient condition using edgewise capacity domination. A cutwise thin-tree statement would be a different, weaker hypothesis and needs its own flow argument; it is not silently assumed here. The complete-graph test shows that arbitrary fractional routing can succeed where this edgewise certificate fails. No general method finding a compatible signing and flow for all subtour points is supplied. All calculations are exact hand proofs, and this duplicate record claims no new independent conjecture or original-target progress.

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 depth-first tree certificate and dense complete-graph flow are proved, but no construction covers every fractional subtour point.

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 53/2021, Combinatorial Optimization, original question and surrounding discussion read from the primary PDF text on 11 October 2026. Historical statements are not a current-status survey. https://ems.press/content/serial-article-files/46931.

Final status

Unresolved in this attempt. The depth-first tree certificate and dense complete-graph flow are proved, but no construction covers every fractional subtour point.

Balanced signing: an explicit Euler-tour flow and the denominator obstruction

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 an undirected graph let $\delta(S)$ be the edges with exactly one endpoint in $S$. In the source's subtour cut relaxation, $x_e\geq0$ and $x(\delta(S))\geq2$ for every nonempty proper $S\subset V$. For an even terminal set $T$, a balanced signing is $s:T\to\{-1,1\}$ with $\sum_{v\in T}s(v)=0$. A capacitated transshipment routes these supplies and demands using edge capacities $x_e$; its cut feasibility condition is $|\sum_{v\in S\cap T}s(v)|\leq x(\delta(S))$ for every $S\subseteq V$.

Statement recorded in the supplied source.

For every point of the subtour-elimination polytope and every even terminal set, does there exist a balanced signing realizable by a capacitated transshipment? [S2]

Scope qualification.

The source passage uses the cut-based relaxation without degree equations. The displayed capacities are the coordinates of the given point; there is no additional scaling of capacities in this question.

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-22.

Short English statement

Choose equally many source and sink terminals so their unit demands can be routed within the subtour point's edge capacities.

Sources

• S1 Ulam AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 30004910 (OWR-8415356-021). 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 $2022$, Oberwolfach Reports, DOI 10.4171/owr/2021/53, pp. 2893--2954 https://doi.org/10.4171/owr/2021/53.
• S3 Combinatorial Optimization, Oberwolfach Reports 53/2021, primary report PDF https://ems.press/content/serial-article-files/46931. 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

For every point of the subtour-elimination polytope and every even terminal set, does there exist a balanced signing realizable by a capacitated transshipment?

A constructive special case

The primary question requires capacities $x$ themselves. We prove an explicit signing and flow when $2x$ describes a connected Eulerian multigraph, and examine why clearing arbitrary denominators does not preserve the unit supplies. The source's broader half-integral discussion is not imported without checking its Eulerian hypothesis.

Euler-tour construction with exact capacities.

Assume $m_e=2x_e$ are nonnegative integers and the multigraph with $m_e$ copies of edge $e$ is connected on the relevant vertices and has even degree at every vertex. It has a closed walk using each edge copy once. For completeness, follow unused edges from any start until returning to it: at a different vertex, the number of used incidences upon an arrival is odd, so an unused edge remains unless all incidences there had odd total, contrary to even degree. This forms a closed trail. If edges remain, connectivity supplies a vertex of this trail incident to an unused component; form another closed trail there and splice it into the first. The number of unused edges decreases, so this process terminates with an Euler tour.

Let $T$ have even size. If $T$ is empty use zero flow. Otherwise mark one occurrence, for example the first occurrence, of every terminal on the cyclic tour. There are $2h$ marks. Give them alternating signs $+1,-1$ in tour order. On the tour segment from mark $i$ to mark $i+1$, send signed flow $+1/2$ in the tour direction if $i$ has positive sign, and $-1/2$ in the tour direction otherwise; indices are cyclic. At an unmarked occurrence the incoming and outgoing signed values coincide, so the divergence is zero. At a marked occurrence the outgoing minus incoming signed values equal its assigned sign. Even though a vertex may occur elsewhere on the tour, those unmarked occurrences contribute zero. Thus the resulting divergence is the required unit sign at each terminal and zero elsewhere. The number of positive and negative marks is equal, so the signing is balanced.

Aggregate signed traversals on each original undirected edge, using an arbitrary reference direction. The absolute aggregate is at most the sum of traversal magnitudes, namely $m_e/2=x_e$. Cancellation can only decrease it. Therefore this is a transshipment within precisely the original capacities, with no appeal to a separate cut-sufficiency theorem. It proves the desired conclusion for this explicitly stated Eulerian special case.

What arbitrary denominator clearing actually gives.

For rational $x$, choose an integer $D$ with $Dx$ integral. The multigraph with multiplicities $2Dx_e$ has even degrees and is connected when the positive-capacity support is connected. The same construction gives unit supplies, but its capacity bound is $Dx_e$. Dividing the flow by $D$ restores capacities $x_e$ and simultaneously divides every nonzero supply by $D$. Those supplies are $\pm1/D$, not the required $\pm1$. Thus denominator clearing alone does not extend the proof with a capacity factor independent of $D$. The missing step is to coordinate sufficiently many terminal markings without increasing edge usage, rather than merely rescale the Euler tour.

Averaging feasible signings does not repair the problem.

The balance and flow constraints are linear once the signs are fixed, but the requirement $s(v)\in\{-1,1\}$ is not convex. If $(s,f)$ is a valid nonempty-terminal construction, reversing all signs and flows gives $(-s,-f)$ within the same capacities. Their average is $(0,0)$, which has no allowed terminal signs. Hence a convex decomposition of capacities into convenient cases, together with an arbitrary signing for each case, does not produce a valid signing by averaging. This does not prove that compatible choices of signs cannot exist; their compatibility is precisely an additional unresolved requirement of that route.

Audit

The primary signing problem and Euler-walk remark on printed page 2946 were inspected visually and in text. The audit checked repeated vertex visits, orientation cancellation, the last-to-first tour segment, empty $T$, and conservation at unmarked occurrences. It also made the even-degree condition explicit: integrality of $2x$ alone does not force every degree to be even after degree equations have been dropped. No experiment or general splitting-off theorem was used. The proof is a known Eulerian mechanism and does not settle arbitrary fractional subtour capacities.

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 exact Eulerian special-case flow is proved, but arbitrary denominators and incompatible sign choices remain obstacles to extending it to every subtour point.

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 53/2021, Combinatorial Optimization, original question and surrounding discussion read from the primary PDF text on 11 October 2026. Historical statements are not a current-status survey. https://ems.press/content/serial-article-files/46931.

Final status

Unresolved in this attempt. The exact Eulerian special-case flow is proved, but arbitrary denominators and incompatible sign choices remain obstacles to extending it to every subtour point.