REVIEW 4 minor 1 cited by
Labeled Trees Generating Separable and Locally Finite Ultrametrics
T0 review · 0 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read A tree must be countable to generate separable or locally finite ultrametrics.
desk verdict A clean, elementary characterization: countability of the vertex set is the sole obstruction to admitting separable and locally finite generated ultrametrics; the König-type ray/star reduction is the genuinely new piece. 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 central object is the labeled tree $(T, l)$, where $l: V(T) \to \mathbb{R}_+$ is non-degenerate, meaning every edge has at least one endpoint with positive label. It generates the ultrametric $d_l(u,v) = \max\{l(w): w \text{ on the unique path from } u \text{ to } v\}$ for $u \neq v$, and $d_l(u,u) = 0$. The arguments are carried by two structural tools: hulls, the smallest subtree containing a given vertex set, which have a path-union description that lets bounded sets be moved into bounded hulls; and König's Infinity Lemma, the graph-theoretic fact that every infinite connected graph has either a vertex of infinite degree or a ray. The infinite-degree vertex is handled by a counting argument on its neighbors, and the ray is handled by requiring labels along the ray to have limsup infinity; together these cases exhaust all ways an infinite hull can arise.
What would settle it
To test Theorem 4, try to build an uncountable tree with a non-degenerate labeling whose every bounded subset is finite; Theorem 4 says this is impossible, so the decisive experiment is to find a bounded subset containing infinitely many vertices, for instance an uncountable star with labels accumulating below some finite level. A concrete check is the countable-union argument: if all sublevel sets $\{v: l(v) \le n\}$ were finite, their union over $n$ could only be countable, so an uncountable tree must have some sublevel set that is infinite, and that sublevel set is bounded.
Extended reading notes
Core claim
The central discovery is Theorem 4: for a tree $T$, the vertex set $V(T)$ is countable if and only if there exists a non-degenerate labeling $l: V(T) \to \mathbb{R}_+$ such that the ultrametric space $(V(T), d_l)$ is locally finite in the sense that every bounded subset is finite. Theorem 2 gives the parallel statement for separability, with a stronger conclusion: if $V(T)$ is countable then every non-degenerate labeling yields a separable $(V(T), d_l)$, while if $V(T)$ is uncountable no labeling can yield a separable space. The proof mechanism is an obstruction at vertices of uncountable degree: an uncountable tree has a vertex $v$ with uncountably many neighbors, and those neighbors form an uncountable discrete subspace unless $v$ carries label zero, in which case a level set of neighbors with labels bounded away from zero still does. Theorem 3 supplies the local version: a generated ultrametric is locally finite exactly when every ray and every star subgraph of the labeled tree generates a locally finite subspace.
Load-bearing premise
The local-finiteness half of the paper rests on the definition that a metric space is locally finite when every bounded subset is finite; if a stricter definition requiring some fixed radius $r$ with singleton balls is imposed, the characterizations would need to be re-examined.
Editorial extensions
If this is right
- For any countable tree, every non-degenerate labeling gives a separable ultrametric space, so separability cannot be destroyed by any choice of labels.
- For any countable tree, a locally finite labeling exists and can be chosen concretely by numbering the vertices and using the numbers as labels.
- No uncountable tree can carry labels that make the generated ultrametric separable, even if the labels are spread out; an uncountable star of neighbors always persists as an uncountable discrete subspace.
- Local finiteness of the whole space is equivalent to local finiteness on every ray and every star subgraph, so obstructions to local finiteness are localized in one-dimensional rays and one-level stars.
- Existence of a locally finite labeling becomes equivalent to separability under all non-degenerate labelings, aligning two otherwise independent metric-space properties.
Reading between the lines
- Beyond the paper, a natural test is whether the same countability criterion survives the stricter definition of local finiteness used in parts of the literature, which requires some $r>0$ with singleton balls; the numbering labeling can be perturbed to keep all distances separated, so the equivalence may persist in modified form.
- Beyond the paper, the ray-and-star criterion suggests an algorithmic route to checking local finiteness: enumerate the rays and stars of a countable tree presentation and test limsup-infinity and finite-sublevel-set conditions separately.
- Beyond the paper, the class of locally finite generated ultrametrics is incomparable with totally bounded generated ultrametrics: a ray labeled by $n$ is locally finite but not totally bounded, while a ray labeled by $1/n$ is totally bounded but not locally finite.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies ultrametric spaces (V(T), d_l) generated by nonnegative real-valued labelings l on trees T, where d_l(u,v) is the maximum label along the unique path joining u and v. The main results are: Theorem 2 characterizes trees admitting a non-degenerate labeling that generates a separable ultrametric space, showing that this is equivalent to countability of the vertex set, and that for countable trees every non-degenerate labeling is separable. Theorem 3 gives a König-lemma-type criterion: the generated ultrametric is locally finite (in the sense of Definition 1, i.e., every bounded set is finite) if and only if the restrictions to every ray and every star subgraph are locally finite. Theorem 4, the central result, states that a tree admits a non-degenerate labeling generating a locally finite ultrametric if and only if its vertex set is countable. The proofs are elementary, with the forward direction of Theorem 4 using an injective labeling by positive integers and the ray/star criteria of Propositions 4 and 5.
Significance. If correct, the paper gives a clean structural dichotomy: countability of the vertex set is the sole obstruction to the existence of labelings generating separable and, under the stated definition, locally finite ultrametric spaces. The proofs are elementary and mostly self-contained, with standard graph-theoretic facts such as König's Infinity Lemma and hull formulas cited appropriately. A notable strength is that the labeling constructed in Theorem 4 is explicit and uniformly discrete, so Theorem 4 remains valid even under the stricter local-finiteness convention mentioned in Remark 1. The separate characterizations for rays and star graphs are simple and potentially useful for future work.
minor comments (4)
- [Section 4, Proposition 5 proof] In the proof of Proposition 5, the sentence 'Since (V(S), d_lS ) is locally bounded' should read 'locally finite'; local boundedness is not the property being used.
- [Section 4, Lemma 5 proof] In the proof of Lemma 5, inequality (22) is asserted for all v in V(H_A), but the boundedness hypothesis only provides the bound for v in A. The intended argument is that for w in V(H_A) one first chooses v in A with w on the path P_{u,v}, applies (21), and then uses the bound for that v. Please correct the quantifier.
- [Section 3, Corollary 1] Corollary 1 is stated without proof; adding a one-sentence derivation from Theorem 2 and Lemma 4 would improve readability.
- [Abstract and Remark 1] Because 'locally finite' is used in a nonstandard sense, consider adding a brief parenthetical in the abstract or introduction pointing to Definition 1, so that readers relying on the stricter convention are alerted immediately.
Circularity Check
No significant circularity: Theorem 4 is derived from the stated definition of local finiteness and standard graph-theoretic lemmas, with no fitted parameters or prediction-by-construction.
full rationale
The paper's central claims, Theorem 2 and Theorem 4, are proved directly from Definition 1 and the definition of d_l in (7). In Theorem 4, the implication (i) => (ii) constructs an injective labeling l(v)=f(v) with values in N, which makes every generated ultrametric uniformly discrete and hence locally finite under Definition 1; the implication (ii) => (i) writes the countable tree as a countable union of bounded balls Br_n(v), each finite by local finiteness. The proof relies on Theorem 3, Propositions 4 and 5, Lemma 5, and Proposition 3, but these are auxiliary results with their own proofs or standard citations (e.g., Kőnig's Infinity Lemma from Diestel) rather than assumptions equivalent to the target theorem. Prior self-citations, such as Proposition 3's hull formula from [13] and Theorem 1's proof from [7], supply elementary graph-theoretic facts that do not encode the separability or local-finiteness characterizations. No fitted parameters, renamed predictions, or uniqueness arguments imported from the authors are present. The construction in the (i) => (ii) direction also works under the stricter definition mentioned in Remark 1, since all vertex labels are distinct positive integers and therefore every bounded set is finite and every sufficiently small ball is a singleton. The derivation chain is self-contained and not circular.
Assumptions & free parameters
assumptions (6)
- standard math Proposition 1: every infinite connected graph has a vertex of infinite degree or contains a ray (König's Infinity Lemma).
- standard math Proposition 3: for A with at least two points, the hull H_A is the union of paths P_{u,v} for v in A minus {u}, for any u in A.
- standard math A countable union of countable sets is countable.
- standard math A discrete subspace of a separable metric space is countable.
- standard math Theorem 1 from [7]: the mapping d_l is an ultrametric if and only if max{l(u), l(v)} > 0 for every edge {u, v} of the tree.
- domain assumption Definition 1: a metric space is locally finite if every bounded subset is finite; Remark 1 notes this definition is not universally accepted.
Cite this review
Pith. "Pith review of Labeled Trees Generating Separable and Locally Finite Ultrametrics." pith.science (2026). https://pith.science/paper/P2J44DMZ
@misc{pith2026250603853,
author = {Pith},
title = {Pith review of: Labeled Trees Generating Separable and Locally Finite Ultrametrics},
year = {2026},
howpublished = {\url{https://pith.science/paper/P2J44DMZ}},
note = {Machine review of arXiv:2506.03853}
}
read the original abstract
We analyze the interplay between labeled trees and the ultrametric spaces they present. We provide characterizations of labeled trees that generate separable ultrametric spaces and those that generate locally finite ultrametric spaces. In particular, we establish an analog of K\"onig's Infinity Lemma for locally finite ultrametric spaces generated by labeled trees.
Forward citations
Cited by 1 Pith paper
-
Hausdorff distance between ultrametric balls
For any ultrametric space, its set of closed balls with the Hausdorff distance inherits discreteness, local finiteness, completeness, compactness, and related properties exactly when the original space has them; separ...
Reference graph
Works this paper leans on
-
[6]
Dovgoshey, O., Kostikov, A.: Locally finite ultrametric spaces and labeled trees. J. Math. Sci.276(5), 614–637 (2023)
work page 2023
-
[1]
Siberian Mathematical Journal60(1), 10–19 (2019)
Berestrovskii, V.N.: On Urysohn’sR tree. Siberian Mathematical Journal60(1), 10–19 (2019)
work page 2019
-
[2]
Expositiones Mathematicae31(4), 334–349 (2013)
Capraro, V.: Amenability, locally finite spaces, and bi-lipschitz embeddings. Expositiones Mathematicae31(4), 334–349 (2013)
work page 2013
-
[3]
Deza, M.M., Deza, E.: Encyclopedia of Distances, 4th edition edn. Springer, Berlin (2016)
work page 2016
-
[4]
Graduate Texts in Mathematics, vol
Diestel, R.: Graph Theory, 5th edn. Graduate Texts in Mathematics, vol. 173. Springer, Berlin (2017)
work page 2017
-
[5]
Annals of Combinatorics26, 613–642 (2022)
Dovgoshey, O., Küçükaslan, M.: Labeled trees generating complete, compact, and discrete ultrametric spaces. Annals of Combinatorics26, 613–642 (2022)
2022
-
[7]
Theory and Applications of Graphs7(2) (2020)
Dovgoshey, O.: Isomorphism of trees and isometry of ultrametric spaces. Theory and Applications of Graphs7(2) (2020). Article 3
2020
-
[8]
Dovgoshey, O.: Totally bounded ultrametric spaces and locally finite trees. arXiv:2502.04228 (2025)
arXiv 2025
Show all 22 references
-
[9]
P-adic Numbers Ultrametr
Dovgoshey, O., Petrov, E.: On some extremal properties of finite ultrametric spaces. P-adic Numbers Ultrametr. Anal. Appl.12(1), 1–11 (2020) 15
2020
-
[10]
arXiv:1610.08282v2, 1–33 (2016)
Dovgoshey, O., Petrov, E., Teichert, H.-M.: Extremal properties and morphisms of finite ultrametric spaces and their representing trees. arXiv:1610.08282v2, 1–33 (2016)
2016 arXiv
-
[11]
Dovgoshey,O.,Petrov,E.,Teichert,H.-M.:Howrigidthefiniteultrametricspaces can be? Fixed Point Theory Appl.19(2), 1083–1102 (2017)
2017
-
[12]
Dovgoshey, O., Rovenska, O.: Ultrametric spaces generated by labeled star graphs. J. Math. Sci.228(2), 182–198 (2025)
2025
-
[13]
Applied General Topology26(1), 163–182 (2025)
Dovgoshey, O., Vito, V.: Totally bounded ultrametric spaces generated by labeled rays. Applied General Topology26(1), 163–182 (2025)
2025
-
[14]
The Electronic Journal of Combinatorics (DS6) (2024)
Gallian, J.A.: A dynamic survey of graph labeling. The Electronic Journal of Combinatorics (DS6) (2024). Dynamic Survey
2024
-
[15]
Gurvich, V., Vyalyi, M.: Ultrametrics, trees, and bottleneck arcs. Math. Ed., Moscow: MCNMO3(16), 75–88 (2012)
2012
-
[16]
Hughes, B.: Trees and ultrametric spaces: a categorical equivalence. Adv. Math. 189(1), 148–191 (2004)
2004
-
[17]
Kainth,S.P.S.:AComprehensiveTextbookonMetricSpaces.Springer,Singapore (2023)
2023
-
[18]
Acta Sci
König, D.: Über eine Schlussweise aus dem Endlichen ins Unendliche. Acta Sci. Math.(Szeged) 3(2–3), 121–130 (1927)
1927
-
[19]
Lemin, A.J.: The category of ultrametric spaces is isomorphic to the category of complete, atomic,tree-like, andrealgraduated latticesLAT*.Algebra Universalis 50(1), 35–49 (2003)
2003
-
[20]
Journal of Mathematical Analysis and Applications474(1), 666–673 (2019)
Ostrovska, S., Ostrovskii, M.I.: On embeddings of locally finite metric spaces into lp. Journal of Mathematical Analysis and Applications474(1), 666–673 (2019)
2019
-
[21]
Ostrovskii, M.I.: Embeddability of locally finite metric spaces into banach spaces isfinitelydetermined.ProceedingsoftheAmericanMathematicalSociety 140(8), 2721–2730 (2012)
2012
-
[22]
Petrov, E., Dovgoshey, A.: On the Gomory-Hu inequality. J. Math. Sci.198(4), 392–411 (2014). Translation from Ukr. Mat. Visn. 10(4):469–496, 2013 16
2014
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.