日本オペレーションズ・リサーチ学会
2021年 秋季研究発表会

2-A-6

Colin de Verdière 型ラプラシアンパラメータとテンセグリティの実現可能次元
01309564

東京大学
東京大学

*大場亮俊
谷川眞一

OBA Ryoshun
TANIGAWA Shin-ichi

A ∈ A− (G), 負固有値数が 1} を考える．
この µ0 (G) の見積もりは難しいとされるが，グラフ G の Colin de Verdière 数 µ(G) とは，GColin de Veridière[3] は A ∈ A− (G) にある条件をの正重み付き一般化隣接行列のスペクトルから定課すとよい振る舞いを見せることを発見した．A ∈まるグラフパラメータである．µ はマイナー単調
S n が (G に関して)Strong Arnold 性 (SAP) を性をもつ．驚くべきことに µ はグラフの位相的な有するとは，S[i, i] = 0 (∀i ∈ V ), S[i, j] = 0性質を反映することが示されている [3, 5]．同種の=(∀ij∈ E), AS = 0 の 3 条件を満たす非ゼロ対代数的パラメータとして ν が導入されている [7]．
称行列 S ∈ S n が存在しないことをいう．Colin de
別の文脈で [1] は，グラフ実現問題の SDP 緩和にVerdière 数をおける低ランク解の存在性を基に，実現可能次元と=
いう幾何パラメータ rd を導入した．[4] は類似のA ∈ A− (G)
=幾何パラメータ gd を導入し，Colin de Verdièreµ(G)=maxdimker
A:
負固有値数が1
型パラメータ ν = と関連付けた．具体的には [4] は半SAP を有する 
正定値行列補間問題の低ランク解の存在性を基にgd= を定義し，SDP の主双対の観点から ν = (G) ≤と定める．すると µ はマイナー単調性をもち，以=gd (G) を示した．
下のようにグラフの位相的な性質を反映する．
本研究では，多重グラフ G に対して，非ゼロ重定理 1 ([3, 5]).
• µ(G) ≤ 2 ⇔ G は外平面的み付きラプラシアン行列のスペクトルから Colin• µ(G) ≤ 3 ⇔ G は平面的
de Verdière 型グラフパラメータ λ(G) を定義する．
• µ(G) ≤ 4 ⇔ G は R3 へリンクなし埋込可能
そして λ がマイナー単調性をもつことを示す．また[7] は Colin de Verdière 型パラメータ ν = をグラフ実現問題の SDP 緩和の主双対の観点から，導入した．グラフ G に対し A(G) ⊂ S n を
λ を幾何パラメータ rd と結びつけ，λ(G) ≤ rd(G)A(G) = {A ∈ S n : A[i, j] = 0 (i ̸= j, ij ̸∈ E)} でを示す．ここで rd(G) は多重グラフ G 上のテンセ定める．グラフパラメータ ν = を
グリティの実現可能性を基に定まるもので，既存}{nのパラメータ rd= (G) の一般化にあたる．さらにA ∈ A(G) ∩ S+=
ν (G) = max dim ker A :三角格子グラフの λ の値を計算することで，λ おSAP を有する
よび rd の木幅との関係性を明らかにする．と定めると，ν = もマイナー単調性をもつ．

1.

はじめに

2.

Colin de Verdière 型パラメータ

以下 G = (V, E) は有限無向グラフとし，V ={1, . . . , n} とする．n × n 実対称行列全体を S n ,n で表す．グラフn × n 半正定値対称行列全体を S+G について A− (G) ⊂ S n を{}A[i, j] < 0 (ij ∈ E)−n
A (G) = A ∈ S :A[i, j] = 0 (i ̸= j, ij ̸∈ E)で定める．A− (G) 内の行列の第二固有値に注目し，その重複度の最大値 µ0 (G) = max{dim ker A :3.

SDP と実現可能次元

グラフ G と頂点配置 p : V → Rd (d ∈ N) の組(G, p) に対し，次の SDP の実行可能性問題 P(G, p)を考える:
nFind X ∈ S+s.t.
⟨X, Fij ⟩ = ∥p(i) − p(j)∥2 (∀ij ∈ E)

ただし，Fij = (ei − ej )(ei − ej )⊤ とする．P(G, p)
は (G, p) と辺長の等しい頂点配置を求めるグラフ

実現問題の SDP 緩和である．グラフの実現可能次
元 rd= (G) は{}∃X s.t. rank X ≤ d′ ,=′rd (G) = max min d :pP(G, p) の実行可能解

これは (G, σ, p) から変形可能なテンセグリティを記述する．多重グラフの実現可能次元 rd(G) を{}∃X s.t. rank X ≤ d′ ,′rd(G) = max min d :(G,σ,p)
P(G, σ, p) の実行可能解で定まる．ここで p は任意次元の任意の頂点配置を渡る．rd= は自明にマイナー単調性をもつ．
[4] は類似の幾何パラメータ gd= を導入した．
Sd−1 ⊂ Rd を d − 1 次元球面とする．G と p : V →S d−1 の組に対して次を考える:

で定める．rd もマイナー単調性をもつ．Connellyの超安定性定理 [2] より次が成り立つ．

nFind X ∈ S+s.t.
Xij = p(i)⊤ p(j) (i = j or ij ∈ E)

定理 3. 任意 G について，λ(G) ≤ rd(G) である．
さらに λ, rd はグラフの木幅と関係する．サイズr の三角格子グラフを ∆r と表す．rd= (∆r ) = r −1(r ≥ 3) が [6] により得られていたが，λ(∆r ) の下からの評価と定理 3 から少し強い次が従う．
定理 4. r ≥ 3 について，λ(∆r ) = rd(∆r ) = r − 1.

定理 4 とグリッドマイナー定理より，λ およびこれは半正定値行列補間問題である．これに対し=rd の log と木幅の log が定数倍しか違わないことて同様の方法で，幾何パラメータ gd (G) が定まる．[4] は上の SDP の双対問題を考えることで， が従う．
ν = (G) ≤ gd= (G) という関係を示した．
参考文献

4.

本研究の結果J ∈ S n を全要素 1 の行列とする．多重グラフ G上の辺重み ω : E → R の重み付きラプラシアン
行列を LG,ω で表す．非ゼロ辺重み ω : E → R̸=0に対する LG,ω 全体を L∗ (G) で表す．L ∈ L(G) がEuclidean SAP を有するとは，S(L + J) = 0,
⟨S, (ei − ej )(ei − ej )⊤ ⟩ = 0 (∀ij ∈ E) を満たす非ゼロ対称行列 S ∈ S n が存在しないことをいう．
パラメータ λ を，連結多重グラフ G に対して，}{n,L ∈ L∗ (G) ∩ S+λ(G) = max dim ker L :Euclidean SAPとし，λ(G) = max{λ(H) : H は G の連結成分 }と定める．このとき以下が成り立つ．
定理 2. λ はマイナー単調性をもつ．
次に λ の双対にあたる幾何パラメータを定義する．多重グラフ G と符号関数 σ : E → {±1} の組(G, σ) であって，どの多重辺上でも σ が一定でないものを符号グラフという．符号グラフ (G, σ) とp : V → Rd の組 (G, σ, p) をテンセグリティという．テンセグリティ(G, σ, p) に対して次を考える:
nFind X ∈ S+s.t.
⟨X, Fij ⟩ ≤ ∥p(i) − p(j)∥2 (σ(ij) = +1)⟨X, Fij ⟩ ≥ ∥p(i) − p(j)∥2 (σ(ij) = −1).

[1] M. Belk and R. Connelly. Realizability ofgraphs. Discrete & Computational Geometry,
37(2):125–137, 2007.
[2] R. Connelly. Rigidity and energy. Invent.
math., 66(1):11–33, 1982.
[3] Y. Colin de Verdière. Sur un nouvel invariant
des graphes et un critere de planarité. Journalof Combinatorial Theory, Series B, 50(1):11–21, 1990.
[4] M. Laurent and A. Varvitsiotis. A new graphparameter related to bounded rank positive
semideﬁnite matrix completions. Mathematical Programming, 145(1-2):291–325, 2014.
[5] L. Lovász and A. Schrijver. A borsuk theorem
for antipodal links and a spectral characterization of linklessly embeddable graphs. Proceedings of the American Mathematical Society, 126(5):1275–1285, 1998.
[6] G. Joret S. Fiorini, H. Tony and C. Muller.
Unavoidable minors for graphs with large ℓp dimension. Discrete & Computational Geometry, pages 1–43, 2021.
[7] H. van der Holst. Topological and spectral
graph characterizations. PhD thesis, University of Amsterdam, 1996.