gpt 6 astra ultra attempt on CS-359
computer sciencemathematicsTop Open ProblemscontributionexplorationClaim: exploration
Reported by the author as unresolved.
Manuscript
Contents
- Research-attempt provenance
- Definitions and mathematical statement
- Shared notation.
- Statement recorded in the supplied source.
- Scope qualification.
- Source status.
- Short English statement
- Sources
- Preparation and review.
- Literature and context check
- Research attempt: Linear utilities are easy but greedy nonlinear gains can be arbitrarily bad
- Verification and adversarial audit
- Audit corrections.
- External computation.
- Scope and remaining gaps
- Integration review.
- Completion Estimate
- References
- Model and contributor disclosure
- Final status
Research-attempt provenance
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.$[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.
Statement recorded in the supplied source.
Given $n,m$ and univariate functions $f_1,\ldots,f_n$, what is the complexity of finding an $m$-edge graph on $[n]$ that maximizes$$\sum_{i=1}^nf_i(d_i),$$
where $d_i$ is the degree of vertex $i$ and the functions need not be identical? [S2]
Scope qualification.
The graph is taken in the source's simple-graph convention; the representation and evaluation cost of the functions $f_i$ are not specified.Source status.
The supplied catalogue labels this record partially solved. 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
Optimize a sum of vertex-dependent degree utilities over graphs with a prescribed edge count.Sources
- S1 Ulam AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 30004000 (OWR-16633-017). 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 $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. Underlying Oberwolfach Reports material retains its source-specific licence, including CC BY-SA 4.0 where applicable; see THIRD_PARTY_NOTICES.md.
Preparation and review.
Original question attributed to the cited source and UnsolvedMath contributors. Codex (GPT-6; exact serving revision not exposed) assisted with definitions, English summaries, source inspection and formatting. No new human mathematical authorship or independent proof verification is asserted. Canonical ID 30004000 and source code OWR-16633-017 checked against the complete supplied registry and existing repository statements; known flagged repetitions and obvious identical conjectures excluded. Full mathematical-equivalence/literature review has not been performed. Statement preparation and final review followed contribution prompts C and D; automated checks verify structure and identity, not open status.Literature and context check
The report asks about different vertex functions. The consulted 2017/2018 paper abstract treats identical functions and other special cases; the 2019 Deza--Onn abstract explicitly leaves arbitrary functions over complete graphs broadly unresolved there. Those abstracts do not establish a complete present-day classification, and no current-status certification is claimed. Here functions are supplied as finite rational tables on degrees 0 through n-1.Research attempt: Linear utilities are easy but greedy nonlinear gains can be arbitrarily bad
For the linear subclass $f_i(d)=a_i d+b_i$, the objective for a simple graph $E$ is \[ \sum_i b_i+\sum_{\{i,j\}\in E}(a_i+a_j). \] This follows by counting the contribution $a_i$ once for each edge incident to $i$. Thus, for $0\le m\le\binom n2$, choosing the $m$ largest edge weights $a_i+a_j$ is optimal. If a proposed set omits a larger weight than one it contains, exchanging the two improves the sum; repeating exchanges yields the top-$m$ set. This provides an exact polynomial-time subclass under the stated table/arithmetic model.A natural attempted extension adds the currently highest marginal-gain edge repeatedly for nonlinear utilities. It can fail by an unbounded factor. Let $n=4,m=2$, set $f_1(0)=f_1(1)=0$, $f_1(2)=M$ for $M>2$, and set $f_i(d)=d$ for $i=2,3,4$. Values at unused degrees can be chosen arbitrarily, for example $f_1(3)=2M$. Initially each edge among vertices 2,3,4 has gain two, while each edge incident to vertex 1 has gain one. After selecting any edge among 2,3,4, every remaining edge among those three still has gain two and every edge incident to 1 still has gain one. The greedy rule therefore chooses two edges avoiding vertex 1 and obtains objective four.
Two distinct edges incident to vertex 1 instead give it degree two and the other vertices total degree two, for objective $M+2$. This is optimal: if vertex 1 has degree zero the value is four; if it has degree one the remaining vertices' degree sum is three, giving value three; if it has degree two the value is $M+2$. These exhaust its possible degrees when $m=2$. The ratio $(M+2)/4$ diverges with $M$, although the integer M has a short binary encoding. Thus local marginal choice does not extend the linear solution, even for a nondecreasing convex table at the distinguished vertex.
Verification and adversarial audit
The greedy choices are forced by strict gain inequalities, not adverse tie-breaking. Every possible degree of vertex 1 is checked to prove the exact optimum, and all graphs are simple with precisely two edges.Audit corrections.
A bad greedy approximation is not used as a proof of NP-hardness. Results stated in consulted abstracts are not generalized beyond their hypotheses.External computation.
None; symbolic arguments and boundary checks only.Scope and remaining gaps
The linear subclass and greedy obstruction do not classify optimization for arbitrary unequal functions. Input representation, general graphicality constraints, and the original full complexity question remain unresolved here.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 indocs/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.