gpt 6 astra ultra attempt on CS-359

Research-attempt provenance

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.

$[n]=\{1,\ldots,n\}$ and $d_i$ is the number of edges incident to vertex $i$. The objective assigns a separate scalar utility to each vertex's degree.

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: This record repeats the graph-complexity question represented canonically and with its objective by OWR-16633-017. No separate clean statement is promoted; the original record remains publicly visible and retained for provenance.

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

For graphs, given n,m and vertex functions f_1,

\textbackslash{}

ldots,f_n, what is the complexity of finding an m-edge graph maximizing

\textbackslash{}

sum_{i=1}^n f_i$d\_i$ when the functions are not necessarily identical? [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-21.

Short English statement

The supplied fragment concerns duplicate Degree-Utility Graph Optimization Problem. Its complete mathematical target is not recovered.

Sources

• S1 Ulam AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 30004001 (OWR-16633-018). 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 $2019$, Oberwolfach Reports, DOI 10.4171/owr/2018/50, pp. 2969--3023 https://doi.org/10.4171/owr/2018/50.
• S3 Optimization over Degree Sequences of Graphs https://arxiv.org/abs/1908.09278.
• S4 Optimization over Degree Sequences https://arxiv.org/abs/1706.03951.
• Source-specific Oberwolfach Reports licences, including CC BY-SA 4.0 where applicable, are retained; see THIRD_PARTY_NOTICES.md.

Preparation and review.

The original source and UnsolvedMath contributors retain attribution for the source extract. Codex (GPT-6; exact serving revision not exposed) assisted with definitions, English summaries, scope notes and formatting. No new human mathematical authorship or independently verified solution is asserted. Permanent source ID 30004001 and code OWR-16633-018 checked against the complete supplied registry and current repository. Distinct upstream records, including repeated questions and broad or damaged extracts, are retained for complete coverage of the source CS category. A repeated record is not a new independent conjecture. Complete mathematical-equivalence and current-literature review has not been performed. Related canonical identities: 30004000. Preparation and final review follow contribution prompts C and D, with source gaps disclosed. Structural and rendering checks do not establish a new theorem or open status.

Literature and context check

This is the retained duplicate of the unequal degree-utility question. The original report and the two listed degree-optimization abstracts were consulted. A different failed algorithmic route is investigated here, without presenting the duplicate as a new problem.

Research attempt: Independent degree optimization can choose a nongraphical vector

One might optimize degrees independently subject only to $0\le d_i\le n-1$ and $\sum_i d_i=2m$, then realize the resulting sequence. Those necessary constraints are insufficient. For $n=4,m=3$, the vector $(3,3,0,0)$ satisfies both, yet is not the degree vector of a simple graph: a degree-three vertex must be adjacent to all other vertices, contradicting either vertex of degree zero.

This obstruction can be forced as the unique optimizer of the relaxed utility problem. Give vertices 1 and 2 utility one exactly at degree three and zero at other degrees; give vertices 3 and 4 utility one exactly at degree zero and zero at other degrees. The relaxed vector $(3,3,0,0)$ has objective four, and any different vector loses at least one of the four indicator rewards, so it is uniquely optimal in the relaxation. No graph attains value four by the preceding contradiction.

The exact graph optimum is one. To prove an upper bound, suppose a graph has a degree-three vertex among 1 and 2. All other vertices then have positive degree, so neither zero-degree reward can occur. If both vertices 1 and 2 had degree three, their incident edges would include their common edge and four further distinct edges, at least five edges, impossible with $m=3$. Thus this case yields at most one reward. If neither distinguished vertex has degree three, only vertices 3 and 4 can give rewards. They cannot both be isolated, since the remaining two vertices support at most one simple edge, fewer than three. Again there is at most one reward. A three-edge star centered at vertex 1 gives one reward, proving attainability.

The gap four versus one is not an integrality gap for a claimed sophisticated polyhedral formulation; it belongs to the explicitly weakened degree-sum relaxation. Adding a realization oracle after optimization detects the failure but does not by itself find the best realizable sequence. The first missing algorithmic step is how to enforce joint graphicality while optimizing all unequal utility tables, rather than assuming the handshake constraint is enough.

Verification and adversarial audit

The degree-sum and degree-bound checks are explicit, the relaxed optimum is unique, and the graph optimum is proved by exhausting the reward possibilities. Both the five-edge obstruction and the isolated-pair obstruction use the simple-graph convention.

Audit corrections.

The relaxation is named precisely, and nongraphical degree vectors are not treated as feasible graph certificates. The explicit optimum comparison avoids an unsupported hardness inference.

External computation.

None; symbolic arguments and boundary checks only.

Scope and remaining gaps

The duplicate source target remains unresolved in its full generality. The manuscript supplies an exact counterexample to an independent-degree route, not a complexity classification or a new duplicate conjecture.

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 calculations below the preserved source statement investigate a concrete route, but establish no substantiated new progress toward the entire original target. Known special cases and failed sufficient conditions are not credited as a solution.

References

The original source references and catalogue attribution are preserved in the Sources section above. The following URLs were actually consulted for this attempt; retention of an additional original reference does not claim fresh consultation of it.

• https://ems.press/content/serial-article-files/46772 (consulted 2026-10-11).
• https://arxiv.org/abs/1908.09278 (consulted 2026-10-11).
• https://arxiv.org/abs/1706.03951 (consulted 2026-10-11).

Model and contributor disclosure

OpenAI gpt-6-astra, requested reasoning configuration ultra, generated this research attempt on 2026-10-11. The exact serving revision is not exposed. Codex GPT-6 performed orchestration, repository-format review, and adversarial mathematical review of the written argument; its exact serving revision is also not exposed. The mathematical route, boundary checks and final adversarial self-audit followed contribution prompts A then B in docs/contribution_prompts.md, after reading CONTRIBUTING.md. Python 3.14.2 assembled the standalone documents; any mathematical computation is specified in Verification. No theorem prover was used. No human mathematical authorship, substantial human proof correction, or independent human proof checking is asserted. Model-assisted review, source retrieval, and structural checks do not establish correctness or novelty. Full private reasoning transcripts are unavailable as reproducibility artifacts; the complete arguments, inputs and outcomes actually used are stated here or in the companion batch audit.

Final status

Unresolved as a new research contribution. This is a concrete route investigation, not a claim of new complete resolution or a current-status certification. A known answer reproduced for context does not become a new contribution. The catalogue's source-status label is preserved; this attempt status does not assert that a source-labelled solved question is open.