REVIEW 5 minor 1 cited by
Ultrametric spaces generated by labeled star graphs
T0 review · 0 major / 5 minor · reviewed 2026-08-09 · deepseek-v4-flash
Pith's one-line read The paper proves that an ultrametric space is generated by a labeled star graph exactly when some point's distances never exceed rival distances, and that the metric isometry group equals the graph automorphism group exactly when the…
desk verdict Clean, correct structural results for star-generated ultrametric spaces; the proof typos are minor and repair without changing the theorems. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The machinery is the labeled star graph $S(l)$—one center adjacent to every other vertex—together with the distance formula $d_l(u,v)=\max_{w\in V(P)}l(w)$, where $P$ is the unique path joining $u$ and $v$; for a star this reduces to a maximum over endpoint labels. The load-bearing criterion is condition (2.1), the existence of a point $x_0$ whose distance to any other point never exceeds any other distance involving that point. The remaining mechanism is order-theoretic: the set $D_0$ of nonzero distances, through whether it has infimum $0$ and whether it has a least element, controls uniqueness of the generating star graph and the equality of isometry and graph-automorphism groups.
What would settle it
Take a four-point ultrametric space with no point $x_0$ satisfying $d(x_0,x)\le d(y,x)$ for all distinct $x,y\ne x_0$ (the spaces in Figure 3 are examples) and enumerate every labeled star graph on four vertices, checking that none reproduces the distance table; Theorem 2.1 would fail if one did. For Theorem 3.2, try to construct a star-generable space whose positive distance set has no least element yet admits a distance-preserving map that moves the center; finding one would disprove the group equality.
Extended reading notes
Core claim
The central discovery is a metric certificate for star generation. Theorem 2.1 states that an ultrametric space $(X,d)$ belongs to the class $\mathbf{US}$—there is a labeled star graph $S(l)$ with $X=V(S)$ and $d=d_l$—if and only if some point $x_0\in X$ satisfies $d(x_0,x)\le d(y,x)$ whenever $x_0\ne x\ne y$. The point $x_0$ acts as a center: every distance from it to another point is no larger than any rival distance to that point from a third point. The paper then proves that the star representation is rigid exactly when the positive distances accumulate at $0$, i.e. $\inf D_0(X)=0$, and that the equality $\operatorname{Iso}(X,d)=\operatorname{Iso}S(l)$ holds for every generating labeled star graph exactly when the set $D_0$ of nonzero distances has no least element. The least-element condition is what prevents a minimally labeled leaf from being swapped with the center to create a metric symmetry invisible to the graph.
Load-bearing premise
The load-bearing premise is that the two results quoted from reference [15]—that the vertex-label maximum rule defines an ultrametric exactly when no edge has two zero labels, and that isomorphisms of labeled trees preserve the generated distances—are valid for infinite trees; the paper uses both as black boxes without re-proving them.
Editorial extensions
If this is right
- Every ultrametric space with at most three points is star-generable, since every ultrametric triangle is isosceles with base no larger than the legs (Corollary 2.1).
- The space $(\mathbb{R}^+,d_+)$ with $d_+(p,q)=\max\{p,q\}$ for $p\ne q$ is a US-space with a unique generating labeled star graph, because its positive distances have infimum $0$ (Examples 2.1 and 2.2).
- Whenever a star-generable space has positive distances accumulating at $0$, every self-isometry of the space is a self-isomorphism of every labeled star graph generating it (Corollary 3.2).
- If the positive distance set has no least element, the equality of the isometry group and the graph-automorphism group still holds; if it has a least element, swapping the center with a minimally labeled leaf produces a self-isometry that is not a graph self-isomorphism (Theorem 3.2).
- Four-point ultrametric spaces need not be star-generable: the two spaces displayed in Figure 3 fail the center-point test and are not in $\mathbf{US}$ (Example 4.1).
Reading between the lines
- A direct algorithmic reading not stated in the paper: condition (2.1) can be checked in quadratic time by precomputing, for each point $x$, its minimal distance to any other point, and then testing whether a candidate $x_0$ stays at or below that minimum for every $x$.
- The construction in Theorem 2.1 is effectively canonical: labels are just distances to the distinguished point, so any finite ultrametric dataset passing the test yields a star model whose vertex labels are measured distances, not free parameters.
- The no-least-element dichotomy implies a practical caveat: in a finite star-generable space, a unique smallest positive distance is exactly what creates metric symmetries that ignore the graph, so graph-based symmetry counts should be trusted only when no such minimum exists.
- The compactness conjecture points to a testable boundary: an infinite star-generated space should be compact exactly when its leaf labels can be arranged as a sequence decreasing to $0$; checking whether the metric alone forces such an ordering would clarify the transition from star models to ray models.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies the class US of ultrametric spaces that arise as (V(S), d_l) for a star graph S with a nonnegative, non-degenerate vertex labeling l, where d_l(u,v) is the maximum label on the unique path between u and v. Theorem 2.1 gives a metric characterization: an ultrametric space (X,d) belongs to US iff there is a point x0 such that d(x0,x) ≤ d(y,x) whenever x0 ≠ x ≠ y. Theorem 2.2 characterizes, for US-spaces, when the generating labeled star graph is unique up to isomorphism: this happens exactly when inf D0(X) = 0. In Section 3, Theorem 3.1 relates self-isometries of the ultrametric space to isomorphisms of the generating labeled trees, and Theorem 3.2 shows that Iso(X,d) = Iso S(l) for every generating labeled star graph S(l) iff the set D0(X,d) has no least element. The paper closes with examples and two conjectures concerning finite four-point obstructions and compactness of infinite US-spaces.
Significance. The results are clean and checkable: Theorem 2.1 is a genuinely simple metric criterion, and Theorem 3.2 gives a complete answer to a natural rigidity question for star-generated ultrametric spaces. The proofs are constructive and there are no fitted parameters or ad hoc assumptions. The paper depends on two lemmas imported from the first author's earlier paper [15], namely Theorem 1.1 and Proposition 3.1; I checked their application to possibly infinite star graphs and found them elementary and correct, so I do not see a circularity or correctness risk. The contribution is modest and incremental, but it is solid and should be of interest to researchers working on ultrametrics and labeled trees.
minor comments (5)
- [§2, Theorem 2.2 proof] Inequality (2.33) is asserted for every n, but its left side is 0 when x_n = c1; the argument should split into the cases x_n = c1 and x_n ≠ c1, applying the inequality on a subsequence or switching to y_n if necessary. The adjacent use of (2.3) to derive d(c_i,x_n) ≤ d(x_n,y_n) needs the same caveat for x_n = c_i, where the inequality is trivial rather than an instance of (2.3).
- [§3, Theorem 3.2 proof, Eq. (3.34)] The displayed equality D0(X,d*) = 0 should be inf D0(X,d*) = 0, since after subtracting a non-attained infimum the value 0 is not actually a distance; this is exactly the hypothesis needed for Corollary 3.2, so the correction does not affect the rest of the proof.
- [§3, Theorem 3.1 proof, (ii)⇒(i)] The proof says 'Let T2(l2) be a labeled star graph generating (X,d)', although the theorem is stated for arbitrary labeled trees; the same argument works for labeled trees, so the wording should be corrected.
- [§1, imported lemmas] Theorem 1.1 and Proposition 3.1 are quoted from [15] without proof; both are short and their extension to infinite star graphs is immediate, but for self-containedness the authors should either include proofs or restate the needed results explicitly.
- [§2, Theorem 2.2 statement] Statement (ii) is worded as 'S1(l1) are isomorphic to S2(l2)'; it should read 'S1(l1) and S2(l2) are isomorphic', and similarly in the proof.
Circularity Check
No significant circularity; central proofs are constructive and imported lemmas are independent.
full rationale
The derivation chain is self-contained for the paper's central claims. Theorem 2.1 proves both directions directly: (i)->(ii) reads off the center inequality from the definition d_l(c,x)=max{l(c),l(x)} <= max{l(y),l(c),l(x)} for a star, and (ii)->(i) constructs the labeling l(x)=0 at x0 and l(x)=d(x0,x) otherwise, then verifies d=d_l using the strong triangle inequality and the defining inequality (2.1); no quantity is fitted from the data it is asked to predict. Theorem 2.2 likewise proves uniqueness from inf D0 = 0 by direct limit arguments and the identity d(c,x)=l(x) when l(c)=0. The remaining group theorems rely on Theorem 1.1 and Proposition 3.1, imported from [15] by the first author, but these are elementary, parameter-free lemmas whose stated assumptions concern labeled-tree isomorphism and non-degenerate labelings, not the article's target claims. They are used as independent support, not as conclusions smuggled into premises. The typo in (3.34) (D0(X,d*)=0 instead of inf D0(X,d*)=0) is repairable and does not make the argument circular. There are no fitted parameters, no prediction of a subset from which a parameter was fit, and no uniqueness assertion imported solely from authors' prior authority. Score 0.
Assumptions & free parameters
assumptions (4)
- domain assumption Theorem 1.1: d_l is an ultrametric on V(T) iff max{l(u), l(v)} > 0 for every edge {u,v} (non-degenerate labeling).
- domain assumption Proposition 3.1: an isomorphism f of labeled trees T1(l1) and T2(l2) yields d_l1(u,v)=d_l2(f(u),f(v)) for all u,v.
- standard math Standard ultrametric facts: every triangle is isosceles with base no larger than the equal sides, and convergent sequences have unique limits.
- standard math The infimum of the empty set in [0,+infinity] is +infinity.
Cite this review
Pith. "Pith review of Ultrametric spaces generated by labeled star graphs." pith.science (2026). https://pith.science/paper/LBTJ7VTD
@misc{pith2026250201260,
author = {Pith},
title = {Pith review of: Ultrametric spaces generated by labeled star graphs},
year = {2026},
howpublished = {\url{https://pith.science/paper/LBTJ7VTD}},
note = {Machine review of arXiv:2502.01260}
}
abstract
For arbitrary star graph $S$ with a non-degenerate vertex labeling $l\colon V(S) \to \mathbb{R}^+$ we denote by $d_l$ the corresponding ultrametric on the vertex set $V(S)$ of $S$. We characterize the class $\bf US$ of all ultrametric spaces $(V(S), d_l)$ up to isometry. We also find the necessary and sufficient conditions under which the group of all self-isometries of ultrametric space $(V(S), d_l)$ coincides with the group of all self-isomorphisms of the labeled star graph $S(l)$.
Figures
Figures from the paper (1 more)
Forward citations
Cited by 1 Pith paper
-
Totally bounded ultrametric spaces and locally finite trees
Totally bounded ultrametric spaces are represented, up to isometry of their completions, by locally finite labeled trees whose vertices are open balls labeled by their diameters.
Reference graph
Works this paper leans on
-
[15]
O. Dovgoshey, Isomorphism of trees and isometry of ultrametric spaces, Theory and Applications of Graphs, 7 (2020), no. 2, Art. 3
work page 2020
- [1]
-
[2]
H. Bruhn, and R. Diestel, Duality in infinite graphs , Combinatorics, Probability and Computing, 15 (2006), 75–90
work page 2006
- [3]
-
[4]
H. Bruhn, and M. Stein, Duality of ends , Combinatorics, Probabil- ity and Computing, 19 (2010), no. 1, 47–60
work page 2010
-
[5]
C. Delhomm´ e, C. Laflamme, M. Pouzet, and N. Sauer, Indivisi- ble ultrametric spaces , Topology and its Applications, 155 (2008), no. 14, 1462–1478. 20
work page 2008
-
[6]
Diestel, End spaces and spanning trees, Journal of Combinatorial Theory, Series B, 96 (2006), no
R. Diestel, End spaces and spanning trees, Journal of Combinatorial Theory, Series B, 96 (2006), no. 6, 846–854
work page 2006
-
[7]
Diestel, Locally finite graphs with ends: A topological approach, I
R. Diestel, Locally finite graphs with ends: A topological approach, I. Basic theory , Discrete Mathematics, 311 (2011), no. 15, 1423– 1447
work page 2011
Show all 31 references
-
[8]
Diestel, Ends and Tangles , Abhandlungen aus dem Mathematis- chen Seminar der Universit¨ at Hamburg 87 (2017), 223–244
R. Diestel, Ends and Tangles , Abhandlungen aus dem Mathematis- chen Seminar der Universit¨ at Hamburg 87 (2017), 223–244
2017
-
[9]
Diestel, Graph Theory, fifth ed., Graduate Texts in Mathematics, 173, Springer, Berlin, 2017
R. Diestel, Graph Theory, fifth ed., Graduate Texts in Mathematics, 173, Springer, Berlin, 2017
2017
-
[10]
Diestel, and D
R. Diestel, and D. K¨ uhn, Topological paths, cycles and spanning trees in infinite graphs , European Journal of Combinatorics, 25 (2004), 835–862
2004
-
[11]
Diestel, and J
R. Diestel, and J. Pott, Dual trees must share their ends , Journal of Combinatorial Theory, Series B, 123 (2017), 32–53
2017
-
[12]
Diestel, and P
R. Diestel, and P. Spr¨ ussel, The fundamental group of a locally finite graph with ends , Advances in Mathematics, 226 (2011), no. 3, 2643–2675
2011
-
[13]
Diestel, and P
R. Diestel, and P. Spr¨ ussel, On the homology of locally compact spaces with ends, Topology and its Applications, 158 (2011), no. 13, 1626–1639
2011
-
[14]
Diestel, and P
R. Diestel, and P. Spr¨ ussel, Locally finite graphs with ends: A topo- logical approach, III. Fundamental group and homology , Discrete Mathematics, 312 (2012), no. 1, 21–29
2012
-
[16]
Dovgoshey, and A
O. Dovgoshey, and A. Kostikov, Delhomme–Laflamme–Pouzet– Sauer space as groupoid , Journal of Mathematical Sciences, 284 (2024), no. 3, 315–328
2024
-
[17]
Dovgoshey, and A
O. Dovgoshey, and A. Kostikov, Locally finite ultrametric spaces and labeled trees , Journal of Mathematical Sciences, 276 (2023), no. 5, 614–637
2023
-
[18]
Dovgoshey, and M
O. Dovgoshey, and M. K¨ u¸ c¨ ukaslan,Labeled trees generating com- plete, compact, and discrete ultrametric spaces , Annals of Combi- natorics, 26 (2022), 613–642. 21
2022
-
[19]
Dovgoshey, O
O. Dovgoshey, O. Martio, and M. Vuorinen, Metrization of weighted graphs, Annals of Combinatorics, 17 (2013), 455–476
2013
-
[20]
Dovgoshey, and E
O. Dovgoshey, and E. Petrov, Subdominant pseudoultrametric on graphs, Sbornik: Mathematics, 204 (2013), no. 8, 1131–1151
2013
-
[21]
Dovgoshey, and E
O. Dovgoshey, and E. Petrov, On some extremal properties of fi- nite ultrametric spaces , p-Adic Numbers, Ultrametric Analysis and Applications, 12 (2020), no. 1, 1–11
2020
-
[22]
Dovgoshey, and E
O. Dovgoshey, and E. Petrov, Weak similarities of metric and semi- metric spaces, Acta Mathematica Hungarica, 141 (2013), 301–319
2013
-
[23]
Dovgoshey, E
O. Dovgoshey, E. Petrov, and H.-M. Teichert, On spaces extremal for the Gomory-Hu inequality , p-Adic Numbers, Ultrametric Anal- ysis and Applications, 7 (2015), no. 2, 133–142
2015
-
[24]
Dovgoshey, E
O. Dovgoshey, E. Petrov, and H.-M. Teichert, How rigid the finite ultrametric spaces can be? Journal of Fixed Point Theory and Ap- plications, 19 (2017), no. 2, 1083–1102
2017
-
[25]
Dovgoshey, and V
O. Dovgoshey, and V. Shcherbak, The range of ultrametrics, com- pactness, and separability , Topology and its Applications, 305 (2022), 107899
2022
-
[26]
Dovgoshey, and V
O. Dovgoshey, and V. Vito, Totally bounded ultrametric spaces gen- erated by labeled rays , arXiv:2402.15774, 2024
2024 arXiv
-
[27]
Gurvich, and M
V. Gurvich, and M. Vyalyi, Characterizing (quasi-)ultrametric fi- nite spaces in terms of (directed) graphs , Discrete Applied Mathe- matics, 160 (2012), no. 12, 1742–1756
2012
-
[28]
Ishiki, Constructions of Urysohn universal ultrametric spaces , p- Adic Numbers, Ultrametric Analysis and Applications, 15, ( 2023), no
Y. Ishiki, Constructions of Urysohn universal ultrametric spaces , p- Adic Numbers, Ultrametric Analysis and Applications, 15, ( 2023), no. 4, 266–283
2023
-
[29]
A. J. Lemin, On Gelgfand’s problem concerning graphs, lattices, and ultrametric spaces , AAA62 Workshop on General Algebra –
-
[30]
Petrov, and A
E. Petrov, and A. Dovgoshey, On the Gomory-Hu inequality , Jour- nal of Mathematical Sciences, 198 (2014), no. 4, 392–411. CONTACT INFORMATION 22 Oleksiy Dovgoshey Institute of Applied Mathematics and Mechanics of NASU, Slo vyansk, Ukraine, Department of Mathematics and Statis...
2014
-
[62]
Arbeitstagung Allgemeine Algebra (Linz, Austria), Jun e 2001, pp. 12–13
2001
Reviewed August 9, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.