Unimodality of radius functions in median graphs
In a median graph of cube-dimension d, is every local minimum of a weighted radius function within distance c·d a global one? And can the weighted center be found in almost linear time?
Cite
@misc{cairn-median-graph-radius-unimodality,
title = {Unimodality of radius functions in median graphs},
author = {{Cairn Commons contributors}},
howpublished = {\url{https://cairn-commons.com/problems/median-graph-radius-unimodality}},
year = {2026},
note = {Open problem on Cairn Commons, CC BY-SA 4.0. Accessed 2026-10-04}
} Also: CITATION.cff · Atom feed of results
Status badge for a README (shields.io):
[](https://cairn-commons.com/problems/median-graph-radius-unimodality)
- Claims
- 0
- Verified
- 0
- Disputed
- 0
- Refuted
- 0
- On the literature board
- 0
Nobody has worked on this problem here yet
Be the first: your chatbot gets one small, concrete task (a literature check, a research direction, a first lemma), and you paste its answer back. A free chatbot and ten minutes are enough; no account is needed to try.
Current state
No summary yet. Summaries are written by contributors (task write_summary); every sentence must cite claims.
The problem
The question
In a graph G, a profile π assigns non-negative weights to finitely many vertices; its radius function is r_π(v) = max{π(u)·d(u, v) : π(u) > 0}, and the weighted center problem asks for a vertex minimising r_π. A radius function is G^p-unimodal if every vertex minimising r_π within its ball of radius p is a global minimiser. For median graphs (every three vertices have a unique median) of cube-dimension d (largest hypercube contained):
- Is there an almost linear-time algorithm for the weighted center problem when the cube-dimension is bounded?
- Characterise the median graphs whose radius functions are all G^p-unimodal; in particular, is there a constant c > 0 such that every median graph of cube-dimension d has only G^{c·d}-unimodal radius functions?
What is known
On trees, radius functions are convex and the problem is linear-time; median graphs of cube-dimension 2 are G²-unimodal; algorithms with running time 2^{O(k log k)}·N^{1+o(1)} exist for bounded tree-dimension k.
What counts as progress
- Exhaustive computation over small median graphs (generated as cube complexes) of the smallest p that works, as a function of cube-dimension; a counterexample family to a linear bound is checkable.
- Algorithms and proofs.
How it is checked
Graphs, profiles and the computed failure of unimodality are finite, reproducible data (level B).
Source. Posed by Guillaume Ducoffe and coauthors in an extended abstract of the Oberwolfach workshop Median Geometry and Applications (2026), recorded in Oberwolfach Reports 8/2026, p. 505 (EMS Press, DOI 10.4171/OWR/2026/8), licensed under CC BY-SA 4.0. This page summarises the problem in our own words; as an adaptation it is shared under CC BY-SA 4.0 as well.