Radius-Function Unimodality in Bounded-Dimensional Median Graphs

Definitions and mathematical statement

For a connected unweighted graph $G$, let $d_G(u,v)$ denote shortest-path distance and let \[ I_G(u,v)=\{x\in V(G):d_G(u,v)=d_G(u,x)+d_G(x,v)\}. \] The graph is a median graph if, for every triple $u,v,w\in V(G)$, the intersection \[ I_G(u,v)\cap I_G(v,w)\cap I_G(w,u) \] contains exactly one vertex. The hypercube $Q_n$ has vertex set $\{0,1\}^n$, with two vertices adjacent when they differ in exactly one coordinate. The cube dimension of a median graph is the supremum of the integers $n\geq 0$ for which $Q_n$ embeds isometrically in the graph. A partial cube is a graph admitting an isometric embedding into a hypercube.

Main question, with unresolved source terminology. Does there exist an absolute constant $c>0$, independent of the graph, its cube dimension $d$, and the radius function, such that every median graph of cube dimension $d$ has every one of its radius functions $G_{cd}$-unimodal?

The supplied excerpt does not define either the family of radius functions or the predicate $G_k$-unimodal. In particular, the notation $G_{cd}$ is retained as source notation and is not identified here with any particular graph construction. The excerpt also does not specify whether graphs must be finite, how to interpret a nonintegral parameter $cd$, or whether dimension zero is included. Consequently, the question above preserves the supplied target but is not yet a fully specified mathematical proposition.

Further directions stated in the source. Investigate extensions of the preceding theory to edge-weighted median graphs. The source anticipates additional assumptions on the weights and suggests assigning a common positive weight to all edges in each $\Theta$-class. For an unweighted partial cube, edges $ab$ and $xy$ belong to the same $\Theta$-class precisely when \[ d_G(a,x)+d_G(b,y)\ne d_G(a,y)+d_G(b,x). \] Thus the suggested condition is that a weight function $w:E(G)\to(0,\infty)$ be constant on each such class; different classes may have different weights. The excerpt does not assert that this condition suffices or specify the desired weighted conclusion.

The source also proposes extending the preceding results to useful families of unweighted partial cubes, suggesting the identification of families with median closures of subquadratic size. It does not specify the closure construction, its ambient space, or the size parameter. It additionally reports a recent conditional quadratic lower bound for $\ell_1$-spaces, citing an unidentified reference [1]; the precise lower-bound statement and its assumptions are absent. These are research directions rather than fully quantified additional conjectures in the supplied record.

Short English statement

The main question asks whether one universal constant makes every radius function on a median graph unimodal in the source's $G_{cd}$ sense, with the parameter proportional to cube dimension. The meanings of radius function and $G_k$-unimodality must be recovered before this becomes a precise standalone conjecture. Weighted median graphs and unweighted partial cubes are additional proposed directions, with substantial hypotheses and targets left unspecified.

Sources

• Supplied local registry record, permanent UnsolvedMath ID $30006606$, source problem code catalogue entry, titled Radius-Function Unimodality in Bounded-Dimensional Median Graphs. The project identifies data/unsolvedmath/problems.json and the supplementary registry catalog/problems.json; this draft uses the supplied record without independently inspecting either file. No individual proposer is identified.
• Median Geometry and Applications (2026), Oberwolfach Reports, report 8/2026, pp. 487--540, DOI 10.4171/owr/2026/8. Supplied report link: https://doi.org/10.4171/owr/2026/8. The excerpt labels the main question "Open problem 2" and gives the additional directions under "Perspectives."
• Dragan et al., G-unimodality of radius functions, supplied literature-source link: https://arxiv.org/abs/2503.15011. The record supplies no further bibliographic details or explicit mapping from this reference to the definitions missing from the excerpt.
• Literature assessment dated exactly 2026-08-22: supplied dated curation, not independently verified. It labels the problem open and states that the report records the cube-dimension-two case, while no general constant $c$ is established. The record says the report and the Dragan et al. reference were checked during that curation, and explicitly requests independent verification of time-sensitive status and cited claims.
• The original excerpt attributes a conditional quadratic lower bound for $\ell_1$-spaces to reference [1]. The identity of [1], its conditional hypothesis, and its precise conclusion are not supplied.