線形代数で考える スペクトラル・グラフ理論入門

• P.13: χ が未定義で現れますが，χ = chr です．

• P.15: log(n-1) -> log(d-1)

• P.16: log(n-1) -> log(d-1)

• P.33, 命題3.21のあと:  存在する例えば -> 存在する．例えば

• P.154, 定理11.25の1行前: パスの集合->パスの個数

• P.240, 練習問題9.10の解答中: 

  • グラフはa=0およびc=1という異なる固有値を持つため，強正則グラフである．->グラフは3つの異なる固有値を持つ，パラメータa=0およびc=1の強正則グラフである．

  • 周長->内周

• 第1章：

  •  1.1: グラフの用語が説明されます．特に積グラフ（カルテシアン積とも呼ばれる）の定義，リンクグラフの定義（定理3.22のパラメーターの等しい非同型SRGペアの構成で用いられる）を確認しておこう．

  • 1.2: 2部グラフに関する解説です．定理1.4の2部グラフであることの必要十分条件「奇i数長さのサイクルを持たない」これは以後複数回用いられる．また与えられたグラフから2部グラフを構成するの「2部グラフ化」が解説される．こちらも本テキストでは重要概念となる．

• 第2章：

  • 2.1: 彩色数と独立数の定義・性質が述べられる．

  • 2.2: 直径と内周の定義・性質が述べられる．

  • 2.3: 等周定数の定義・性質が述べられる．

• 第3章：

  • 3.1: Cayleyグラフの定義が述べられる．例3.5は2章で紹介された5つの不変量が等しい，非同型グラフペアの構成がなされる．（この一般化はできるだろうか？）彩色数と独立数の定義・性質が述べられる．

  • 3.2: ここではCayleyグラフが頂点推移的であること，以後しばしば用いられるbi-Cayleyグラフの構成が述べられる．

  • 3.3: 強正則グラフの定義・性質が紹介される．定理3.22のパラメーターの等しい非同型SRGペアの構成だ．（こちらの一般化は可能だろうか？）

  • 3.4: 強正則グラフの2部グラフ版であるデザイングラフの定義・性質が紹介される．

• 第4章：

  • 4.1: 

  • 
    

• 第5章：

  • 
    
  • 
    

• 第6章：

  • 6.4: Paley グラフの universality が解説されます．グラフが n-universal とは，任意の n 頂点単純グラフに対して，それを誘導部分グラフとして含むグラフです．Paley グラフ P(q) に対して，q を十分大きくとれば n-universal となることが証明されます．この事実からこちらの論文の元となるアイデアを得ました．

• 第7章：

  • 
    

• 第8章：

  • 
    

• 第9章：

  • 
    

• 第10章：

  • 10.4: グラフとその部分グラフの固有値の関係が示されます．それを用いて，Petersen graph がハミルトンでないことを証明します．（こちら議論を適用可能な，非ハミルトングラフの無限系列を与えることはできるか？）

• 第11章：

  • 11.3: スペクトラムを用いてグラフの辺数を評価します．応用として有限体上の方程式の解の個数の評価式を得ます．グラフとは全く関係なさそうな問題を，グラフと関連付けてスペクトラル・グラフ理論で解決する，この分野の醍醐味が力説されます．

• 第12章：

  • 
    

1. Noga Alon, Tools from higher algebra

2. L´aszl´o Babai and P´eter Frankl, Linear algebra methods in combinatorics

3. Brouwer, Andries E.(NL-EIND-M); Haemers, Willem H.(NL-TILB-EOR) Spectra of graphs. Universitext Springer, New York, 2012. xiv+250 pp. ISBN:978-1-4614-1938-9 (Brouwer 先生のホームページ版)

4. Leran Cai, Everything about Spectral Graph Theory

5. Derek Chen and Advay Goel, Spectral Graph Theory

6. Fan R. K. Chung, Lectures on Spectral Graph Theory

Chapter 1. Eigenvalues and the Laplacian of a graph

1.1. Introduction 

1.2. The Laplacian and eigenvalues 

1.3. Basic facts about the spectrum of a graph 

1.4. Eigenvalues of weighted graphs 

1.5. Eigenvalues and random walks 

Chapter 2. Isoperimetric problems 

2.1. History 

2.2. The Cheeger constant of a graph 

2.3. The edge expansion of a graph 

2.4. The vertex expansion of a graph 

2.5. A characterization of the Cheeger constant 

2.6. Isoperimetric inequalities for cartesian products 

Chapter 3. Diameters and eigenvalues 

3.1. The diameter of a graph 

3.2. Eigenvalues and distances between two subsets 

3.3. Eigenvalues and distances among many subsets 

3.4. Eigenvalue upper bounds for manifolds 

Chapter 4. Paths, flows, and routing 

4.1. Paths and sets of paths 

4.2. Flows and Cheeger constants 

4.3. Eigenvalues and routes with small congestion 

4.4. Routing in graphs 

4.5. Comparison theorems 

Chapter 5. Eigenvalues and quasi-randomness 

5.1. Quasi-randomness 

5.2. The discrepancy property 

5.3. The deviation of a graph 

5.4. Quasi-random graphs

7. Dragos Cvetkoviˇc and Slobodan K. Simiˇc, Spectral graph theory in computer science

8. Akihito Hora , Nobuaki Obata, Quantum Probability and Spectral Analysis of Graphs

9. Jiaqi Jiang, An introduction to spectral graph theory

1. Introduction 

2. Background of Spectral Graph Theory 

3. Basic Properties of The Laplacian Matrix 

4. Eigenvalues and Eigenvectors of the Laplacians of Some Fundamental Graphs 

5. The Bounding of λ 

6. Further Discussion on Simple Path Counting Problem 

10. 垣村尚徳，グラフと線形代数：グラフスペクトルとその周辺

11. Lele Liu and Bo Ning, Unsolved Problems in Spectral Graph Theory

12. Jason Miller, An Introduction to Spectral Graph Theory

1 Introduction 

2 Some Introductory Graph-Theoretic Definitions

3 Motivating Question 

4 Number of Walks and the Adjacency Matrix 

5 The Laplacian Matrix and Connectedness 

6 The Matrix-Tree Theorem 

7 Conclusion 

13. スペクトラルクラスタリング

14. スペクトラルグラフ理論を利用した産業クラスターの検出日本の原油価格

15. Nica, Bogdan(3-MGL) A brief introduction to spectral graph theory. EMS Textbk. Math. European Mathematical Society (EMS), Zürich, 2018. viii+156 pp. ISBN:978-3-03719-188-0 (arXiv 版)

16. Tim Roughgarden and Gregory Valiant, Spectral Graph Theory, I

17. Sakami, スペクトラルクラスタリング解説

18. Daniel Spielman, Spectral Graph Theory 

19. Daniel Spielman, Spectral Graph Theory and its Applications

20. Daniel Spielman, Spectral and Algebraic Graph Theory

21. Hiroshi Suzuki, Lecture Note on Terwilliger Algebra (Terwilliger 先生の講義録です)

22. tmtk, スペクトラルクラスタリング入門