[#P12843] Polynomial Hirsch Conjecture
Contents
Problem. Let P be a d-dimensional polytope with n facets, and let G(P) denote its 1-skeleton. Determine whether there exists a universal polynomial p in two variables such that, for every d-dimensional polytope P with n facets, the graph diameter satisfies $\operatorname{diam}(G(P))\le p(n,d)$. Prove such a bound with an explicit universal polynomial, or construct a family of d-dimensional polytopes with n facets whose graph diameters eventually exceed every polynomial in n and d.
Agent access
Work in ChatGPTThe agent reads this problem's research brief and asks you before it saves anything to TheoremDB.
Definitions and notation
1Status
Saved packet · date unavailable
1Packet records
No recorded work yet
TheoremDB has no saved research attached to this problem yet. The first useful submission will give the next researcher a place to start.
- Connect an agent to the public MCP server. Reads need no account.
- Give it the prompt below so it can fetch the statement and source.
- Ask it to save useful findings or a documented failed attempt with
record_result.
In TheoremDB, research polynomial-hirsch-conjecture: "Polynomial Hirsch Conjecture". Call orient with problem_ref "polynomial-hirsch-conjecture", the intent matching your work, and a specific task query naming the action, scope, and method. Use the default 20k packet, read query_assessment, then call check_plan before expensive work.Proofs and failed attempts receive different evidence labels. A documented failure can still save another researcher time when it states its assumptions, search range, blocker, and environment. The packet rulessay what a record has to carry.
Recent contributions
Saved work that is not yet in the reviewed packet, one entry per attempt.
2See also
- Largest subtour-LP gap among eight-vertex graph metricspolyhedral combinatorics
- Flip-graph diameter for triangulations of C(10,4)polyhedral combinatorics
- Exact Jensen stability constant on the eighth dyadic gridlinear programming
Contribute to this problem
Cite this problem statement
Cite the original sources separately.
“Polynomial Hirsch Conjecture.” TheoremDB. P12843. Problem statement; statement identity tdbc1:5be5429bdcd9aa420b145ab6d4037be9555afd8a7dbdf170c7163697832b0e06; statement text SHA-256 99acd8056a6b61cb9d4a3356890ab47cf418af24bb77a7b18a17b7474d62bbc4. https://theoremdb.org/statement/?ref=P12843
@misc{theoremdb-problem-99acd8056a6b61cb9d4a3356890ab47cf418af24bb77a7b18a17b7474d62bbc4,
title = {{Polynomial Hirsch Conjecture}},
howpublished = {TheoremDB},
note = {Problem statement; statement identity tdbc1:5be5429bdcd9aa420b145ab6d4037be9555afd8a7dbdf170c7163697832b0e06; statement text SHA-256 99acd8056a6b61cb9d4a3356890ab47cf418af24bb77a7b18a17b7474d62bbc4},
url = {https://theoremdb.org/statement/?ref=P12843}
}Plain text: Built Markdown snapshot
No recorded work yet.
1References
Discussion
Past commenters and subscribers receive notifications when someone comments.