The Polynomial Hirsch Conjecture

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.

The one-skeleton of a polyhedron has its vertices as nodes and its edges as graph edges. Diameter is the maximum shortest-path distance between pairs of vertices in this graph.

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. This is another source record for the Polynomial Hirsch target already catalogued under ID 44; it does not assert an additional independent conjecture.

Source-record limitation: Duplicate Polynomial Hirsch target, already present under canonical ID 44.

Related catalogue records: 44. Separate source IDs are preserved for their provenance.

Statement recorded in the supplied source.

Is the diameter of the $1$-skeleton of every polyhedron bounded by a polynomial in its number $n$ of facets and its dimension $d$? [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

Bound polyhedral graph diameter polynomially in dimension and number of facets.

Sources

• S1 Ulam AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 30003994 (OWR-16633-011). 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 On Circuit Diameter Bounds via Circuit Imbalances https://link.springer.com/article/10.1007/s10107-024-02107-x.
• 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 30003994 and code OWR-16633-011 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: 44. 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

The report, pp. 3013--3014, distinguishes the polynomial Hirsch question from well-conditioned special classes and random-polytope routes. The following adversarial check concerns a common failed inference from a long constructed path to graph diameter. It gives no new diameter bound for arbitrary polyhedra.

Research attempt: Long walks do not certify large polyhedral diameter

For the cube $[0,1]^d$, vertices are binary strings and edges change exactly one coordinate. Two strings differing in $h$ coordinates have graph distance $h$: any path must change each differing coordinate at least once, giving the lower bound; changing those coordinates one at a time attains it. Hence the diameter is exactly $d$, and the cube has $2d$ facets.

Nevertheless the same graph has a simple path visiting all $2^d$ vertices. Construct a list recursively. In dimension one use $0,1$. Given a list $G_{d-1}$ in which consecutive strings differ in one coordinate, list first $0G_{d-1}$ and then $1$ followed by the reversal of $G_{d-1}$. Within each half adjacency is inherited. At the join, the two strings have identical suffixes and differ only in the leading bit. No string repeats because each half has distinct suffixes and their leading bits differ. Thus the list is a Hamiltonian path of length $2^d-1$.

This exact example disproves the inference that an exponentially long valid edge traversal forces exponentially large graph diameter. Diameter minimizes over paths for each endpoint pair; a traversal rule can take a long detour. The constructed path is not claimed to be monotone for a linear objective or to arise from any particular simplex pivot rule. Indeed in dimension two its order $00,01,11,10$ cannot be strictly increasing for one linear objective: the first move requires a positive second-coordinate coefficient, while the last requires it negative. A claimed pivot lower bound would therefore require its own verified construction.

Products supply another boundary check. For graphs of cubes, distances add across coordinate blocks by the same count-of-differing-coordinates proof, so forming many product factors increases diameter additively even while multiplying the number of vertices. Exponential vertex counts and long generated walks are both insufficient substitutes for a lower bound on shortest paths. The missing step toward the source question is control of shortest paths for arbitrary facet systems, not merely exhibiting complicated traversal behavior.

Verification and adversarial audit

The cube's adjacency, lower and upper distance bounds, Hamiltonian recursion, and non-monotonicity in dimension two are explicitly checked. The example is a bounded polytope within the source class and refutes only the stated inference, not the polynomial Hirsch conjecture.

Audit corrections.

A long path is distinguished from a shortest path, and an arbitrary Hamiltonian traversal is not called a simplex pivot path.

External computation.

None; symbolic arguments and boundary checks only.

Scope and remaining gaps

No original-target diameter bound or counterexample is obtained. General polyhedra, including the source's conditioning and random-polytope directions, remain beyond this known elementary example and its route diagnosis.

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

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.