修士論文 要旨

Characterizing the Universal Rigidity of Tensegrities and thed-realizability of Periodic Graphs（テンセグリティの普遍剛性と周期グラフの d-実現可能性の特徴づけ）
数理情報学専攻 48196206
指導教員

大場 亮俊
谷川 眞一 准教授

1 はじめに距離制約をもつネットワークは科学・工学の諸分野に(P) max.
s.t.

現れる．例としてセンサーネットワーク，分子，構造物などがある．これらはテンセグリティとして数学的にモデル化され，各辺の辺長制約を記述した半正定値計画問題 (以下，SDP) を用いて解析が行われている．このSDP の実行可能解の唯一性はテンセグリティの普遍剛性とよばれ，解析の理論保証において重要な役割を果た

0⟨X, Fij ⟩ ≥ ∥p(i) − p(j)∥2⟨X, Fij ⟩ = ∥p(i) − p(j)∥2⟨X, Fij ⟩ ≤ ∥p(i) − p(j)∥2⟨X, 1n 1⊤
X ⪰ 0.
n ⟩,(σ(ij) = −)(σ(ij) = 0)(σ(ij) = +)ただし，Fij = (ei − ej )(ei − ej )⊤ とする．(G, σ, q) が()(G, σ, p) の変形であることと q(i)⊤ q(j) i,j が (P) の実行可能解であることは同値なことに注意する．テン

している．本研究ではまず一般的なテンセグリティにセグリティ (G, σ, p) が普遍剛性をもつとは，(P) の実対して普遍剛性の特徴づけを与えた．さらにこの結果行可能解が唯一であることと定める．(P) の双対問題はを群対称性をもつテンセグリティについて一般化した．

次で与えられる:

次に，辺長制約を表す SDP の低ランク解の存在性に関連する，グラフの d-実現可能性を扱った．本研究で(D) min.
s.t.

はこの概念を周期グラフに拡張し，d = 1, 2 に対して禁∑ω ∥p(i) − p(j)∥2ij∈E(G)∑ ij

LG,ω = ij∈E(G) ωij Fij ⪰ 0σ(ij)ωij ≥ 0 (ij ∈ E(G)).

止マイナーによる特徴づけを得た．

双対問題を用いて普遍剛性の十分条件が与えられる [3]．

2 テンセグリティの普遍剛性

命題 1. (i), (ii) を満たすテンセグリティ (G, σ, p) は普テンセグリティとは，ストラット (伸びるが縮まな遍剛性をもつ:い)，棒材 (伸び縮みしない)，ケーブル (縮むが伸びな(i) (D) の最適解 ω で，rank LG,ω = |V (G)| − d − 1 かい) のピン接合によって構成される構造物である．数学つ ω(e) ̸= 0 (σ(e) = ±) を満たすものが存在する．

的にはグラフ G = (V, E), 符号関数 σ : E → {−, 0, +},(ii) (p(i) − p(j))⊤ S(p(i) − p(j)) = 0 (∀ij ∈ E) なる非頂点配置 p : V → Rd の組として定義される．符号が−/0/+ の辺はストラット/棒材/ケーブルに対応する．
σ ≡ 0 のものをフレームワークとよぶ．以下グラフの頂点数を n で表す．簡単のため n ≥ d + 2 であり，頂点配置のアフィン次元は d とする．2 つのテンセグリティについて (G, σ, q) が (G, σ, p) の変形であるとは，∥q(i) − q(j)∥≥= ∥p(i) − p(j)∥≤(σ(e) = −),(σ(e) = 0),(σ(e) = +)を満たすことをいう．テンセグリティ (G, σ, p) に対して，次の SDP を考える:

ゼロ対称行列 S ∈ Rd×d は存在しない．

(i), (ii) を満たすテンセグリティを超安定的であるとよぶ．超安定性は確認しやすく，普遍剛性のよい十分条件である．ではどのような場合にこの二つが一致するだろうか．頂点配置 p が Q 上代数的独立であることを一般的であるとよぶ．[4] は次を示した．
命題 2. 一般的なフレームワークについて，普遍剛性をもつならば超安定的である．

[4] は射影を用いて普遍剛性および超安定性を幾何的に記述し，命題 2 の主張を半正定値錐の面構造の解析に還元した．これが証明の重要なステップとなっている．

Characterizing the Universal Rigidity of Tensegrities and the d-realizability of Periodic Graphs （テンセグリティの普遍剛性と周期グラフの d-実現可本研究では命題 2 を二つの方向に拡張した．まずストラットやケーブルも含む場合へ拡張した．
定理 3. 一般的なテンセグリティについて，普遍剛性をもつならば超安定的である．
続いて群対称テンセグリティに結果を拡張した．
定義 4. Γ を有限群とする．(G, σ, p) を d 次元テンセ
グリティ，θ : Γ → O(Rd ) を群準同型とする．(G, σ, p)が θ-対称であるとは，Γ が Aut(G) に自由に作用し，σが Γ-不変であり，θ(γ)p(i) = p(γ · i) (i ∈ V (G), γ ∈ Γ)が成り立つことをいう．

Γ が自明群でないとき群対称テンセグリティは一般的ではないが，対称性で割った上での一般性は考えることができる．Γ, θ について，QΓ,θ で Γ の実既約表現の成分と θ(γ) の成分から生成される Q の有限拡大体を表す．θ-対称なテンセグリティ (G, σ, p) が対称性を除い必ず折り畳めることをいう．これは任意の頂点配置 pに対して (P) がランク d 以下の実行可能解をもつこととも言い換えられる．d-実現可能なグラフ全体はマイナーに関して閉じており，禁止マイナーによる特徴づけが期待される．実際 d = 1, 2, 3 の場合のリストが，{K3 }, {K4 }, {K5 , K2,2,2 } であることが分かっている[1, 2]．
本研究ではこの概念を周期グラフ (正確にはその商グラフであるゲイングラフ) に対して拡張した．ルー
プなし多重有向グラフ G = (V, E) とその可逆な辺ラベル z : E → Z の組 (G, z) を (Z-) ゲイングラフとよぶ．周期フレームワークとは，ゲイングラフ (G, z),頂点配置 p : V (G) → Rd , 格子ベクトル l ∈ Rd の組 (G, z, p, l) のことをいう．これに対して次の SDP(Pper ) を考える:
max. 0s.t.
⟨X, Fij′ ⟩ = ∥p(j) − p(i) + z(ij)l∥2
Xn+1,n+1 = ∥l∥2n+1X ∈ S+.て一般的であるとは，各頂点軌道からの代表点の座標がQΓ,θ 上代数的に独立であることをいう．
定理 5. θ : Γ → O(Rd ) を群準同型，(G, σ, p) を対称性を除いて一般的な θ-対称テンセグリティとする．このとき (G, σ, p) が普遍剛性をもつならば超安定的である．

′
ただし，Fij=()
ej − ei (⊤(ij ∈ E))(ej − ei )zij とする．
zij
ゲイングラフ (G, z) が周期 d-実現可能であるとは，任意の p, l について (Pper ) がランク d 以下の実行可能解をもつことをいう．ゲイングラフに対してもマイナーを定義することができ，周期 d-実現可能なゲイングラ

二つの主結果に共通するアイデアは，錐を変形し，変フ全体はマイナーによって閉じている．我々は d = 1, 2

形後の錐の面構造を解析し，[4] の議論を用いるというに対して，禁止ゲインマイナーがそれぞれ {(K2= , z) :ものである，定理 3 では，不等式制約のためにそのまま∀z} ∪ {(K3 , 0)}, {(K3== , z) : ∀z} ∪ {(K4 , 0)} であるの形では射影を用いた言い換えができない．そこでスことを示した．ただし，K2= は二重辺の 2 頂点グラフ，ラック変数を導入して高次元空間の錐に変形する．定K3== は二重辺 2 つの 3 頂点グラフを表す．

理 5 では，まず半正定値錐を群対称な部分に制限する．
次にこの群対称錐の面構造の解析のため，実既約表現分解を用いて制限した錐を半正定値錐，複素半正定値錐，四元数半正定値錐の直和に変形する．
定理 5 の錐の変形は，SDP のブロック対角化 [5] から着想を得た．これは SDP の係数行列に対称性がある場合，それらを同時ブロック対角化し計算量を削減する手法である．今回は，θ-対称なテンセグリティについて，(P) を係数行列が対称性をもつ形に変形し，その後[5] と同じ変換を試みた．

3 周期グラフの d-実現可能性
グラフ G が d-実現可能であるとは，任意の次元のフレームワーク (G, p) が辺長を変えずに d 次元空間に

参考文献[1] M. Belk. Realizability of graphs in three dimensions.
Discrete & Computational Geometry, 37(2):139–162,
2007.
[2] M. Belk and R. Connelly. Realizability of graphs.
Discrete & Computational Geometry, 37(2):125–137,
2007.
[3] R. Connelly. Rigidity and energy. Invent. math.,
66(1):11–33, 1982.
[4] S. Gortler and D. Thurston. Characterizing the universal rigidity of generic frameworks. Discrete Comput. Geom., 51(4):1017–1036, 2014.
[5] K. Murota, Y. Kanno, M. Kojima, and S. Kojima. A
numerical algorithm for block-diagonal decompositionof matrix * -algebras with application to semideﬁnite
programming. Jpn. J. Ind. Appl. Math., 27(1):125–160, 2010.