gpt 6 astra ultra attempt on CS-387

Repeated top-k matching question: failure of a matroid-greedy interpretation

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.

A perfect matching is a set of disjoint edges covering every vertex exactly once. If its edge weights in nonincreasing order are $w_1\geq\cdots\geq w_t$, its top-$k$ objective is $\sum_{i=1}^kw_i$, with $0\leq k\leq t$. The input weights are finitely encoded, and polynomial time is measured in their binary length and the graph size.

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 top-k perfect-matching question retained in OWR-8415356-025. No separate clean mathematical statement is supplied; this source ID preserves its provenance.

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

It remains open if we can get a deterministic polynomial-time algorithm for this problem. In addition, the complexity of the problem (without restrictions on the edge-weights) remains open. Open problem: Perfect matching that maximizes the k-heaviest edges Ola Svensson [S2]

Source status.

The supplied catalogue labels this source record partially solved; 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 deterministic Optimization of Top-k Perfect-Matching Edges. Its complete mathematical target is not recovered.

Sources

• S1 Ulam AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 30004915 (OWR-8415356-026). 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 Exact matching and top-k perfect matching https://arxiv.org/abs/2209.09661.
• S4 Restricted top-k matching algorithms https://arxiv.org/abs/2510.12552.
• Source-specific Oberwolfach Reports licences, including CC BY-SA 4.0 where applicable, are retained; see THIRD_PARTY_NOTICES.md.

Verbatim supplied catalogue question

It remains open if we can get a deterministic polynomial-time algorithm for this problem. In addition, the complexity of the problem (without restrictions on the edge-weights) remains open. Open problem: Perfect matching that maximizes the k-heaviest edges Ola Svensson

The original problem behind the trailing fragment

The primary source identifies this text as the continuation of the bipartite top-$k$ perfect-matching question retained in 30004914. It does not introduce a new independent problem. We test whether the source's extendable-edge-set formulation defines a matroid, which would justify a simple weight-greedy algorithm. It does not, as the following fully specified bipartite example shows.

The hereditary family and its failed exchange axiom.

Let a six-cycle have alternating edge sets $A=\{a_1,a_2,a_3\}$ and $B=\{b_1,b_2,b_3\}$. Its only perfect matchings are $A$ and $B$: the choice of which edge covers one vertex forces the next uncovered vertex's choice successively around the cycle. Therefore the family $\mathcal I$ of edge sets extendable to a perfect matching consists exactly of all subsets of $A$ and all subsets of $B$. It is hereditary, because a subset of a set contained in a perfect matching is still contained in that matching.

Take $I=\{a_1\}$ and $J=\{b_1,b_2\}$. Both belong to $\mathcal I$ and $|I|<|J|$. But adding either element of $J\setminus I$ to $I$ gives a set containing an edge of each alternating class, and neither perfect matching contains such a set. Thus no such addition lies in $\mathcal I$, violating the matroid augmentation axiom. This proof does not depend on whether the chosen two edges already share endpoints: sharing endpoints would also prevent extension, and the exact family description covers both possibilities.

The corresponding greedy optimization failure.

Give $a_1$ weight ten, $a_2,a_3$ weight zero, and every $b_i$ weight six. For $k=2$, a greedy procedure that repeatedly chooses the largest-weight edge preserving extendability first chooses $a_1$. It can then extend its selected set only within $A$, so its two-edge score is ten. The two-edge subset $\{b_1,b_2\}$ is extendable to $B$ and has score twelve. The best top-two perfect matching is $B$, also with score twelve, because the two available perfect matchings have scores ten and twelve. Hence a feasible-extension oracle does not by itself make descending-weight greedy exact.

The source's subset equivalence remains valid: the $k$ heaviest edges of any matching form an extendable $k$-set, and any extendable $k$-set has weight at most the top-$k$ total of a matching extending it. What fails is the extra exchange property needed to optimize that family by the matroid greedy theorem. Replacing extension tests by a matching algorithm does not repair the absent exchange axiom.

Audit and missing deterministic mechanism

The primary paragraph on printed page 2948 and its continuation were inspected. The audit kept the graph bipartite, enumerated all perfect matchings by the forcing argument, and distinguished an extendability decision procedure from weighted optimization over extendable sets. All numbers and matching choices were checked by hand; no solver or randomized algorithm was run. The example refutes this specific deterministic greedy route but provides no complexity lower bound or uniform polynomial algorithm for varying $k$. That original task remains unresolved under this duplicate source 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 extendable-edge family is hereditary but not a matroid, and exact extension tests do not make greedy top-k optimization correct; the source deterministic question remains unresolved.

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 extendable-edge family is hereditary but not a matroid, and exact extension tests do not make greedy top-k optimization correct; the source deterministic question remains unresolved.