Values of Travelling-Polytope Constants on Median Graphs

Definitions and mathematical statement

In the usual graph-theoretic terminology, for vertices $u,v$ of a connected graph with graph distance $d$, put \[ I(u,v)=\{w:d(u,w)+d(w,v)=d(u,v)\}. \] A graph is median if, for every three vertices $u,v,w$, the intersection $I(u,v)\cap I(v,w)\cap I(w,u)$ contains exactly one vertex. The supplied record does not specify whether only finite median graphs are intended or whether additional graph conventions are required.

The original statement supplies the following formal expression: \[ \operatorname{TP}(X):=\sup\left\{\alpha\;\Bigm|\; \exists C>0,\ \forall x,y,\ \forall F,\quad \operatorname{TP}(x,F,y)+|F| \geq C\left(\operatorname{TS}(x,F,y)+|F|\right)\alpha \right\}. \] Here the final $\alpha$ is transcribed in the position supplied by the original text. It is unresolved whether this denotes multiplication or is a corrupted exponent intended to give $C(\operatorname{TS}(x,F,y)+|F|)^\alpha$. The functions $\operatorname{TP}(x,F,y)$ and $\operatorname{TS}(x,F,y)$, the admissible domains of $x,y,F,\alpha$, the meaning of $|F|$, and the scalar domain of $C$ are not defined in the supplied record. In particular, finite-set restrictions, empty-set cases, and conventions for an empty or unbounded supremum are unspecified. Consequently, this expression does not yet define a precise invariant from the supplied evidence alone.

Subject to resolving these omissions, the original question asks to determine \[ \{\operatorname{TP}(X):X\text{ is a median graph in the intended class}\}. \] The supplied normalized statement additionally asks, for each possible value $t$, to characterize the median graphs $X$ satisfying $\operatorname{TP}(X)=t$. This characterization request is explicit in the normalized statement but not in the supplied original question. A complete mathematical formulation requires clarification of the invariant and its domains.

Short English statement

Determine the possible values of the supplied travelling-polytope constant on median graphs; the normalized statement also requests a characterization of the graphs attaining each value. The defining quantities, quantifier domains, and placement of $\alpha$ are unresolved, so this is a statement-only draft requiring mathematical review.

Sources

• Local UnsolvedMath registry, permanent ID $30006617$, source problem code catalogue entry, title: Values of Travelling-Polytope Constants on Median Graphs. The supplied record belongs to the Oberwolfach Reports Open Problems collection. No individual proposer is supplied; the proposed year is recorded as 2026.
• Supplied report citation: Median Geometry and Applications (2026), Oberwolfach Reports, pp. 487--540, DOI 10.4171/owr/2026/8. Supplied link: https://doi.org/10.4171/owr/2026/8.
• Supplied literature source, labeled "OWR report": https://ems.press/content/serial-article-files/53603.
• Literature assessment dated exactly 2026-08-22: the supplied curation labels the problem open and states that the record is only the sentence "A natural question is", contains no identifiable mathematical claim, and remains open under the queue rule. This assessment is supplied dated curation, not independently verified. It conflicts with the longer original and normalized statements supplied here. The background itself requests independent verification of time-sensitive status and cited claims.
• The supplied statement-status label is corrected_verified; its accompanying verification note says that only clear formula delimiters, notation, grammar, and typography were repaired, with mathematical content and scope preserved. These are supplied editorial claims, not independent verification of the formula, its definitions, or the problem's mathematical status.