修士論文 要旨ℓp 空間におけるグラフの大域剛性
数理情報学専攻 48226212
指導教員

1 はじめに

杉山 友浩
谷川眞一 准教授

2 ℓp ノルムRd 上のフレームワーク (G, p) とは，単純無向グラフ

以降 d 次元 ℓp 空間を ℓdp と表記する．ノルム空間上

G = (V, E) とその頂点配置 p : V → Rd の組として定のフレームワーク (G, p) が大域剛であるとは， (その義され，建築構造物や分子構造，ロボット制御などを空間のノルムで計測した) 辺長が等しい任意のフレーム記述する数理モデルである．G の構造および各辺の距

ワーク (G, q) について， ある等長変換 η が存在して離の情報だけから，フレームワークの大域的な構造をη(p(i)) = q(i) が任意の i ∈ V (G) について成り立つこ復元する問題を考える．復元が (等長変換の自由度を除ととして定義される．ユークリッド空間 (ℓ2 空間) において) 一意なフレームワークを大域剛であるという．フいて， 連続な等長変換は平行移動 (d 次元) と回転 ( d2

レームワークの大域剛性は， グラフ G の構造と頂点配次元) の任意の組合せであるのに対し， ℓp 空間 (p ̸= 2)置 p の双方に依存し，判定問題は d = 1 の場合であっにおける連続な等長変換の自由度は平行移動の d 次元ても計算量的に困難であることが知られている．こののみである．このようにノルムの違いは等長変換の自困難性を回避するための標準的な処方箋として， 座標由度として現れる．

値 {p(i)k }i∈V,k∈[d] が Q 上で代数的独立であるようなフレームワーク (一般的フレームワークと呼ぶ) に着目( )3 ラプラシアン行列する．Connelly [1] は構造力学で利用される自己応力をℓdp 上のフレームワーク (G, p) に対して，ω : E(G) →重みとしたグラフラプラシアン行列を用いた，一般的

R は 以 下の自己釣り合い条件を満たしているとき，フレームワークの大域剛性の十分条件を示し，その逆(G, p) の自己応力であるという:∑ω(ij)((p(j))k −(p(i))k )p−1 = 0 (u ∈ V (G), k ∈ [d]).

が Gortler-Healy-Thurston [3] によって示された．彼らによって，d 次元一般的フレームワークの大域剛性は，頂点配置 p に依らず，グラフ G の情報のみで決まることが導かれた．また 2 次元ユークリッド空間においては Jackson-Jordán [4] によって，一般的フレームワークの大域剛性に対する組合せ的な特徴付けが与えられている．
前述した問題では辺の情報はユークリッドノルムで与えられていたが，近年では非ユークリッドノルム空間におけるフレームワークの剛性に関する研究が盛んに

v:uv∈E(G)さらに，ある (G, p) の自己応力 ω と k ∈ [d] に対してk 番目の座標に基づく自己応力 ω k : E(G) → R を
ω k (ij) := ω(ij)((p(j))k −(p(i))k )p−2(ij ∈ E(G))と定義する．この ω k によって重みづけられたラプラシアン行列 LG,ωk ∈ RV (G)×V (G) を考える．LG,ωk の各成分はConnelly によってユークリッド空間のフレームワーク∑ j:il∈E(G) ω(il)LG,ω [i, j] = −ω(ij)
0に定義されていた重み付きラプラシアン行列を ℓp 空間と 定 義 さ れ ，全 て の 成 分 が 1 の ベ ク ト ル は カ ーへ一般化し， d 次元 ℓp 空間上の一般的フレームワーク

ネ ル に 含 ま れ る ．さ ら に ω k の 定 義 よ り p(−)k =の大域剛性の十分条件を得た．特に，d = 2 の場合にお{(p(i))k }i∈V (G) もまたカーネルに含まれていることいて条件は必要十分であることを示し，証明を通してがわかる．よって rank LG,ωk ≤ |V (G)| − 2. この不ℓp 平面上の一般的フレームワークの大域剛性に対する等式を等号成立させる自己応力の存在がフレームワー組合せ的な特徴付けを得た．さらに， Erdős-Rényi ラクの大域剛性の十分条件となることを示した．ただンダムグラフがユークリッド空間において大域剛になし， 証明は Gortler-Healy-Thurston [3] がユークリッるための辺のサンプル率に関する Lew [5] らの結果がド空間上の一般的フレームワークの大域剛性の特徴付ℓp 空間についても成り立つことを示した．

けの証明に用いた, Cayley-Menger 代数多様体の ℓp -類行われてきている．本研究では前述した結果の ℓp 空間(p ̸= 2 は正の偶数) に対する類似物を証明した．まず，(i = j)(i ̸= j, ij ∈ E(G))(i ̸= j, ij ∈/ E(G))

ℓp 空間におけるグラフの大域剛性 (杉山 友浩)

似として p-Cayley-Menger 代数多様体を定義し，これが d-identiﬁable となるための特徴付けを調べることで得た．
定理 1. p ̸= 2 を正の偶数, G を |V (G)| ≥ 3 を満たすグラフとする．ある G の ℓdp 上の一般的な頂点配置 pと， フレームワーク (G, p) の自己応力 ω であって任意の k ∈ [d] について rank LG,ωk = |V (G)| − 2 を満たすものが存在すると仮定する．このとき, 任意の ℓdp 上のG の任意の一般的頂点配置 q について， (G, q) は ℓdp 上で大域剛．

5 ランダムグラフの大域剛性
Erdős-Rényi ランダムグラフ G(n, p) とは，n 頂点完全グラフの各辺を確率 p でサンプリングすることで得られるランダムグラフである．Lew ら [5] は Erdős-Rényi ランダムグラフからなる一般的フレームワークがユークリッド空間上で大域剛になるためのサンプリング率の閾値を導出した．本研究ではこの結果が ℓp 空間においても同様に成り立つことを示した．
定理 3. q ̸= 2 を正の偶数とし， d ≥ 1 を自然数とする．また ω(n) を limn→∞ ω(n) = ∞ を満たす任意の4 ℓp 平面における大域剛性の特徴付け
この節では二次元 ℓp 空間上の一般的フレームワーク実関数とする．p∗± (n) := (log n + d log log n ± ω(n))/nとおく．このとき，について考える．グラフ G について， ℓ2p 上で大域剛(i) p > p∗+ (n) であるとき， 任意の d 次元一般的フとなるような一般的配置の存在性に関する特徴付けがレームワーク (G(n, p), p) は漸近的にほとんど確実

Dewar-Hewtson-Nixon [2] によって示されている．こに ℓdq 上で大域剛．の結果と定理 1 を組合せることで任意の一般的フレー(ii) p < p∗− (n) であるとき， 任意の d 次元一般的フ

ムワーク (G, p) が ℓ2p 上で大域剛となるための必要十分

レームワーク (G(n, p), p) は漸近的にほとんど確実条件を与えた．に ℓdq 上で大域剛ではない．

定理 2. p ̸= 2 を正の偶数とし，n ≥ 3 を整数，G を n

この定理から， フレームワークが大域剛となるよう頂点連結グラフとする．このとき，以下は同値である．

な一般的頂点配置が存在するためのサンプリング率の(i) ある 2 次元一般的フレームワーク (G, p) は ℓ2p 上で大域剛．

(ii) 任意の 2 次元一般的フレームワーク (G, p) は ℓp2 上で大域剛．

(iii) 2 次元一般的フレームワーク (G, p) であって，任意の k について rank LG,ωk = n − 2 となるような自己応力 ω を持つようなものが存在する．

(iv) G は 2 連結であって任意の e ∈ E(G) に対してG − e は辺素な 2 本の全域木を持つ．
(iii)⇒(ii) は定理 1, (ii)⇒(i) は自明，(i)⇒(iv) は先行研究 [2] によって示されている. (iv)⇒(iii) の証明は以下の 3 ステップで行った:(Step 1) 条件 (iv) を満たす任意のグラフが，特定の小さいグラフからあるグラフ操作によって生じることを示す [2]; (Step 2) 前述した特定のグラフについて (iii) が成り立つことを示す; (Step3) 前述したグラフ操作によって性質 (iii) が保存されることを示す.
定理 2 より，ℓp 平面における一般的フレームワークの大域剛性は頂点配置に依存せずグラフの性質のみから定まることがわかる．

閾値と，任意の一般的頂点配置についてフレームワークが大域剛となるための閾値は等しいことがわかる．

6 まとめ
p ̸= 2 が偶数の場合における ℓp 空間上の一般的フレームワークの大域剛性に対する特徴付けを与えた．
今後の展望として， p の偶数制約の緩和，および定理 2の d ≥ 3 への一般化が挙げられる．

参考文献[1] Robert Connelly. Generic global rigidity. Discrete &Computational Geometry, 33:549–563, 2005.
[2] Sean Dewar, John Hewetson, and Anthony Nixon.
Uniquely realisable graphs in analytic normed planes.
arXiv preprint arXiv:2206.07426, 2022.
[3] Steven J Gortler, Alexander D Healy, and Dylan P
Thurston.
Characterizing generic global rigidity.
American Journal of Mathematics, 132(4):897–939,2010.
[4] Bill Jackson and Tibor Jordán. Connected rigidity
matroids and unique realizations of graphs. Journalof Combinatorial Theory, Series B, 94(1):1–29, 2005.
[5] Alan Lew, Eran Nevo, Yuval Peled, and Orit E Raz.
Sharp threshold for rigidity of random graphs. Bulletin of the London Mathematical Society, 55(1):490–501, 2023.