2025-11-20T01:25:14.607341

Longest paths in trees and isometricity of ultrametric spaces

Dovgoshey, Rovenska

Let $T$ be a tree of arbitrary finite or infinite order and let $U(T)$ be the set of all ultrametric spaces generated by vertex labelings of $T$. Let ${\bf US}$ denote the class of all ultrametric spaces generated by vertex labelings of star graphs. We prove that the inclusion $U(T)\subseteq {\bf US}$ holds if and only if the longest path in $T$ has a length not exceeding three.

academic

木における最長経路と超距離空間の等距性

基本情報

論文ID: 2510.10038
タイトル: Longest paths in trees and isometricity of ultrametric spaces
著者: Oleksiy Dovgoshey, Olga Rovenska
分類: math.GN（一般位相幾何学）
発表日: 2025年10月14日
論文リンク: https://arxiv.org/abs/2510.10038v1

要旨

$T$ を任意の有限または無限位数の木とし、 $U(T)$ を $T$ の頂点ラベリングから生成されるすべての超距離空間の集合とする。 $\mathbf{US}$ を星グラフの頂点ラベリングから生成されるすべての超距離空間のクラスとする。包含関係 $U(T) \subseteq \mathbf{US}$ が成立することと、 $T$ における最長経路の長さが3以下であることが同値であることを証明する。

研究背景と動機

解決すべき問題：本研究は、特定の等距性条件を満たす木の構造的特徴を刻画することを目的としている。具体的には、以下を満たす木 $T$ を決定することである： $T$ の頂点ラベリングから生成されるあらゆる超距離空間が、ある星グラフの頂点ラベリングから生成される超距離空間と等距同型である。
問題の重要性：
- 超距離空間は数学解析、位相幾何学、応用数学において重要な地位を占める
- 頂点ラベル付き木から生成される超距離空間は、離散構造と距離空間の関係を研究するための新たな視点を提供する
- 星グラフは最も単純な木構造の一つであり、その一般的な木との関係を理解することは複雑な問題の簡略化に役立つ
既存手法の限界：
- 先行研究は主に特定の種類のラベル付き木（星グラフ、射線グラフなど）に焦点を当てている
- 一般的な木構造と星グラフの等価性に関する完全な刻画が欠けている
- 木の組合せ的性質と生成される超距離空間の幾何学的性質との関連性が不明確である
研究動機：木の組合せ構造（特に最長経路の長さ）と、その生成する超距離空間のクラスとの間の正確な対応関係を確立する。

核心的貢献

主定理： $U(T) \subseteq \mathbf{US}$ が成立することと、 $T$ のすべての経路の長さが3以下であることが同値であることを証明した
構造刻画：条件を満たす木の構造を完全に記述した——それらはちょうど星グラフまたは二重星グラフである
理論的関連性：星グラフと二重星グラフの間の新たな相互関連性を確立した（系3.5）
方法論的革新：特定の反例ラベリングの構成と超距離空間の特性を利用して主要な結果を証明した

方法論の詳細

タスク定義

与えられた木 $T$ について、その頂点ラベリングから生成される超距離空間の集合 $U(T)$ と星グラフから生成される超距離空間のクラス $\mathbf{US}$ との間の包含関係を研究する。

核心概念

超距離空間：空でない集合 $X$ 上の関数 $d: X \times X \to \mathbb{R}_+$ であり、以下を満たす：

対称性： $d(x,y) = d(y,x)$
正定値性： $d(x,y) = 0 \Leftrightarrow x = y$
強三角不等式： $d(x,y) \leq \max\{d(x,z), d(z,y)\}$

ラベル付き木から生成される超距離：ラベル付き木 $T(l)$ について、 $l: V(T) \to \mathbb{R}_+$ のとき、以下のように定義される： $d_l(u,v) = \begin{cases} 0, & \text{if } u = v \\ \max_{w \in V(P)} l(w), & \text{if } u \neq v \end{cases}$ ここで $P$ は $u$ と $v$ を結ぶ唯一の経路である。

証明戦略

主定理3.4の証明は3つの同値条件を採用している：

$U(T) \subseteq \mathbf{US}$
$T$ のすべての経路の長さが3以下
次数≥2の頂点が最大2個

主要補題：

補題3.1：長さ≥4の経路が存在する場合、包含関係が成立しないことを反例により証明
補題3.2：次数≥2の任意の2つの頂点は隣接していることを証明
補題3.3：次数≥2の頂点は最大2個であることを証明

技術的革新点

反例構成：補題3.1の証明において、4辺経路上にラベリング $l_2$ （ラベル値2,2,3,2,2）を巧妙に構成し、生成される超距離空間が $\mathbf{US}$ に属さないことを証明した
星グラフ特性化の活用：定理2.5における星グラフから生成される超距離空間の特性を十分に活用した：中心点 $x_0$ が存在して、すべての $x \neq y$ に対して $d(x_0,x) \leq d(y,x)$ が成立する
場合分けによる議論：主定理の証明において、すべての可能な頂点隣接状況を体系的に分析し、議論の完全性を確保した