スペクトルグラフ理論

数学において、スペクトルグラフ理論は、隣接行列やラプラシアン行列など、グラフに関連付けられた行列の特性多項式、固有値、固有ベクトルとの関係におけるグラフの特性を研究する分野です。

単純な無向グラフの隣接行列は実 対称行列であるため、直交対角化可能であり、その固有値は実代数的整数です。

隣接行列は頂点のラベル付けに依存しますが、そのスペクトルはグラフ不変ですが、完全ではありません。

スペクトルグラフ理論は、コリン・ド・ヴェルディエール数など、グラフに関連付けられた行列の固有値の多重度によって定義されるグラフパラメータにも関係します。

2 つのグラフの隣接行列が等スペクトルである場合、つまり、隣接行列が等しい固有値の 多重集合を持つ場合、その 2 つのグラフは共スペクトルまたは等スペクトルと呼ばれます。

共スペクトルグラフは同型である必要はありませんが、同型グラフは常に共スペクトルです。

グラフがスペクトルによって決定されるとは、 と同じスペクトルを持つ他のグラフが と同型である場合に言われます。 ${\displaystyle G}$${\displaystyle G}$${\displaystyle G}$

スペクトルによって決定されるグラフ ファミリの最初の例をいくつか示します。

• 完全なグラフ。
• 有限の星のような木。

グラフのペアが同じスペクトルを持ちながら同型でない場合、そのグラフは共スペクトルメイトであると言われます。

共スペクトルメイトの最小のペアは{ K _1,4 , C ₄ ∪ K ₁ }であり、 1957年にコラッツとシノゴウィッツ^{[1] [2]}によって報告されたように、 5頂点スターと4頂点サイクルと単一頂点グラフのグラフ和集合で構成される。

多面体共スペクトルメイトの最小のペアは、それぞれ8つの頂点を持つ九面体です。 ^[3]

ほとんどすべての 木は共スペクトルである。つまり、頂点の数が増えるにつれて、共スペクトル木が存在する木の割合は1に近づく。^[4]

一対の正則グラフが共スペクトルグラフとなるのは、それらの補グラフが共スペクトルグラフとなる場合のみである。^[5]

距離正則グラフのペアは、交差配列が同じである場合にのみ共スペクトルになります。

コスペクトルグラフは砂田法によっても構築できる。^[6]

共スペクトルグラフのもう一つの重要な情報源は、点共線性グラフと点線幾何学の線交差グラフである。これらのグラフは常に共スペクトルであるが、非同型であることが多い。^[7]

リーマン幾何学の有名なチーガーの不等式には、ラプラシアン行列を伴う離散的な類似物があります。これはおそらく、スペクトル グラフ理論で最も重要な定理であり、アルゴリズムの応用で最も有用な事実の 1 つです。これは、グラフの最も疎なカットを、そのラプラシアンの 2 番目の固有値を通じて近似します。

グラフのチーガー定数（チーガー数または等周数とも呼ばれる）は、グラフに「ボトルネック」があるかどうかを数値的に表す尺度です。「ボトルネック」の尺度としてのチーガー定数は、多くの分野で大きな関心を集めています。たとえば、コンピューターの適切に接続されたネットワークの構築、カードのシャッフル、低次元トポロジー（特に、双曲3次元多様体の研究）などです。

より正式には、 n頂点グラフGのチーガー定数h ( G )は次のように定義される。

${\displaystyle h(G)=\min _{0<|S|\leq {\frac {n}{2}}}{\frac {|\partial (S)|}{|S|}},}$

ここで最小値は最大でn /2個の頂点を持つすべての空でない集合S上で最小値となり、∂( S )はSの辺境界、つまりS内にちょうど1つの端点を持つ辺の集合となる。^[8]

グラフGがd正則な場合、 h ( G ) とGのスペクトルギャップd − λ ₂の間には関係がある。Dodziuk ^[9]およびAlonとMilman ^[10]による不等式は次のように述べている^[11]。

${\displaystyle {\frac {1}{2}}(d-\lambda _{2})\leq h(G)\leq {\sqrt {2d(d-\lambda _{2})}}.}$

この不等式はマルコフ連鎖のチーガー境界と密接に関連しており、リーマン幾何学におけるチーガーの不等式の離散バージョンとして見ることができます。

必ずしも正則ではない一般的な連結グラフについては、Chung ^{[12]によって別の不等式が与えられている: 35}

${\displaystyle {\frac {1}{2}}{\lambda }\leq {\mathbf {h} }(G)\leq {\sqrt {2\lambda }},}$

ここで、は正規化されたラプラシアンの最小の非自明な固有値であり、は（正規化された）チーガー定数である。 ${\displaystyle \lambda}$${\displaystyle {\mathbf {h} }(G)}$

${\displaystyle {\mathbf {h} }(G)=\min _{\emptyset \not =S\subset V(G)}{\frac {|\partial (S)|}{\min({\mathrm {vol} }(S),{\mathrm {vol} }({\bar {S}}))}}}$

ここで、は の頂点の次数の合計です。 ${\displaystyle {\mathrm {vol} }(Y)}$${\displaystyle Y}$

正則グラフの独立集合には固有値の境界があり、これはもともとアラン・J・ホフマンとフィリップ・デルサルトによって発見されたものである。^[13]

が最小の固有値を持つ頂点上の -正則グラフであるとします。このとき、はその独立数を表します。 ${\displaystyle G}$${\displaystyle k}$${\displaystyle n}$${\displaystyle \lambda _{\mathrm {分} }}$$${\displaystyle \alpha (G)\leq {\frac {n}{1-{\frac {k}{\lambda _{\mathrm {min} }}}}}}$$${\displaystyle \alpha (G)}$

この境界は、例えばエルデシュ-コー-ラド定理や有限体上の交差する部分空間族に対するその類似物の代数的証明を確立するために適用されてきた。^[14]

必ずしも正則ではない一般的なグラフの場合、独立数の同様の上限は、 の正規化ラプラシアン^[12]の最大固有値を使用して導くことができます。ここ で、 および はそれぞれにおける最大次数と最小次数を表します。これは、より一般的な不等式 ( ^[12]の 109 ページ) の結果です。 ここで、 は独立した頂点の集合であり、における頂点の次数の合計を表します。 ${\displaystyle \lambda '_{max}}$${\displaystyle G}$$${\displaystyle \alpha (G)\leq n(1-{\frac {1}{\lambda '_{\mathrm {max} }}}){\frac {\mathrm {maxdeg} }{\mathrm {mindeg } }}}$$${\displaystyle {\mathrm {maxdeg} }}$${\displaystyle {\mathrm {mindeg} }}$${\displaystyle G}$$${\displaystyle {\mathrm {vol} }(X)\leq (1-{\frac {1}{\lambda '_{\mathrm {max} }}}){\mathrm {vol} }(G ))}$$${\displaystyle X}$${\displaystyle {\mathrm {vol} }(Y)}$${\displaystyle Y}$

スペクトルグラフ理論は1950年代から1960年代にかけて登場した。グラフの構造的特性とスペクトル特性の関係に関するグラフ理論的研究の他に、量子化学の研究も主要な研究源であったが、これら2つの研究分野のつながりはずっと後になってから発見された。^[15] 1980年のモノグラフSpectra of Graphs ^{[16]はCvetković、Doob、Sachsによってこの分野におけるこれまでのほぼすべての研究を要約している。1988年には、調査研究}Recent Results in the Theory of Graph Spectraによって更新された。^[17] Spectra of Graphsの第3版（1995年）には、このテーマに対する最近のさらなる貢献の要約が含まれている。^{[15] 2000年代に}砂田俊一氏によって考案・開発された離散幾何解析は、重み付きグラフに関連付けられた離散ラプラシアンの観点からスペクトルグラフ理論を扱っており、^[18]形状解析を含むさまざまな分野に応用されています。近年、スペクトルグラフ理論は、多くの実際のアプリケーションでよく見られる頂点変動グラフにまで拡張されています。^{[19] [20] [21] [22]}

• 強正則グラフ
• 代数的接続性
• 代数的グラフ理論
• スペクトルクラスタリング
• スペクトル形状分析
• エストラーダ指数
• ロヴァース・シータ
• エキスパンダーグラフ

• アロン・スペンサー（2011）「確率的方法」、ワイリー。
• アンドリース・ブラウワー; Haemers、Willem H. (2011)、グラフのスペクトル(PDF)、Springer
• Hoory、Linial、Wigderson (2006)、Expander グラフとその応用(PDF)
• チャン、ファン(1997)。アメリカ数学会 (編)。スペクトルグラフ理論。プロビデンス、ロードアイランド州ISBN 0821803158MR 1421568[最初の4章は ウェブサイトでご覧いただけます]{{cite book}}: CS1 メンテナンス: 追記 (リンク)
• Schwenk, AJ (1973)。「ほとんどすべての木は共スペクトルである」。Harary , Frank (編)。グラフ理論の新しい方向性。ニューヨーク: Academic Press。ISBN 012324255X. OCLC  890297242.
• ボグダン、ニカ（2018）。「スペクトルグラフ理論の簡単な入門」チューリッヒ：EMSプレス。ISBN 978-3-03719-188-0。
• Pavel Kurasov (2024)、「グラフのスペクトル幾何学」、Springer(Birkhauser)、オープンアクセス (CC4.0)。

• Spielman, Daniel (2011). 「スペクトルグラフ理論」(PDF)。[組み合わせ科学計算からの章]
• Spielman, Daniel (2007)。「スペクトルグラフ理論とその応用」[FOCS 2007 カンファレンスで発表]
• Spielman, Daniel (2004)。「スペクトルグラフ理論とその応用」[コースページと講義ノート]