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

構成数 : 1

第1章 グラフ
1.1 グラフの概念
1.2 2部グラフ

第2章 不変量
2.1 彩色数と独立数
2.2 直径と内周
2.3 等周定数

第3章 正則グラフ
3.1 Cayleyグラフ
3.2 Cayleyグラフ(続き)
3.3 強正則グラフ
3.4 デザイングラフ

第4章 有限体
4.1 記法
4.2 射影的組合せ論
4.3 インシデンスグラフ

第5章 有限体の平方数
5.1 2次指標
5.2 平方剰余の相互法則
5.3 Paleyグラフ
5.4 bi-Paleyグラフとインシデンスグラフの同型性判定

第6章 指標
6.1 有限Abel群の指標
6.2 有限体上の指標和
6.3 有限体上の指標和について(続き)
6.4 Paleyグラフへの応用

第7章 グラフの固有値
7.1 隣接固有値とラプラシアン固有値
7.2 定義からすぐにわかる性質
7.3 固有値の具体的な計算

第8章 固有値の計算
8.1 Abel群のCayleyグラフとbi-Cayleyグラフ
8.2 強正則グラフ
8.3 重複度の整数性から得られる2つの定理
8.4 デザイングラフ

第9章 最大固有値
9.1 対称行列の最大・最小固有値
9.2 最大隣接固有値
9.3 平均次数
9.4 Tur¥'anの定理のスペクトラル版
9.5 2部グラフのラプラシアン最大固有値
9.6 部分グラフ
9.7 木の最大固有値

第10章 固有値に関するさらなる結果
10.1 対称行列の固有値:Courant-Fischer
10.2 ラプラシアン固有値に関する評価
10.3 対称行列の固有値:CauchyとWeylの定理
10.4 部分グラフ

第11章 スペクトルを用いた評価
11.1 独立数と彩色数
11.2 等周定数
11.3 辺の数え上げ

第12章 最後に
12.1 4-サイクルを持たないグラフ
12.2 Erd¥"os-R¥'enyiグラフ
12.3 Erd¥"os-R¥'enyiグラフの固有値

●付録

付録A 写像,同値関係,商集合,不変量
A.1 写像
A.2 同値関係と商集合
A.3 不変量

付録B 群の基礎
B.1 群の定義
B.2 群の初等的性質
B.3 対称群
B.4 2面体群
B.5 部分群
B.6 部分群の判定条件
B.7 準同型写像の定義
B.8 準同型の像と核
B.9 部分群による剰余類
B.10 右剰余類
B.11 Lagrangeの定理
B.12 正規部分群と剰余群

付録C 環の基礎
C.1 環の定義
C.2 多項式環
C.3 イデアル
C.4 剰余環
C.5 Zの剰余環
C.6 環の準同型写像

付録D 有限体の構成
D.1 既約元
D.2 剰余環が体になる条件
D.3 3次以下の既約多項式の判定法