外書輪講I(第13回)

[場所1E503（月曜日5限）]

HPに行く

現在外書輪講では、Matousekの33-Miniaturesをみんなで読んでいます。

今回は、Miniature 14, 15をやりました。

Miniature 14

内周が $g$ で、最小次数が $r$ となるグラフの中で最小頂点数を

もつグラフの頂点数を $n(r,g)$ とします。

内周が $g=2k+1$ のとき、

$$1+r+r(r-1)+r(r-1)^2+\cdots +r(r-1)^{k-1}\le n(r,g)$$

となります。このイコールが成り立つグラフのことを

Mooreグラフ(ムーアグラフ)といいます。

例えば、内周が5 の場合、ムーアグラフの頂点数は、

$1+r+r(r-1)=r^2+1$ となります。

内周が偶数 $g=2k$ の場合もありますが、そのときは、

$$1+r+r(r-1)+r(r-1)^2+\cdots+r(r-1)^{k-2}+(r-1)^{k-1}\le n(r,g)$$

が成り立ちます。このイコールが成り立つグラフのことを generalized polygon

といいます。

このminiatureでは、内周が5となるムーアグアフの

最小次数 $r$ がスペクトラルグラフ理論により高々3種類に絞られる
という定理について紹介されています。

定理

$G$ が内周が5のムーアグラフであるなら、$G$ の最小次数 $r$ が
$r\ge 3$ であるならば $r\in \{3,5,57\}$ である。

$r=3$ の場合は、前回も登場したペテルセングラフであり、$r=5$ の場合は、

ホフマン-シングルトングラフといいます。

$r=57$ の場合だけ、その存在が未だ保証さていません。

もし存在すれば、頂点数 $3250$ で、最小次数が $57$ で、内周が $5$ の

グラフになります。

もし発見できれば、発見者の名前が付けられて 誰々のグラフということに

なるのではないでしょうか？

ムーアグラフは、正則グラフになることを注意しておきます。

つまり、最小次数とはいえ、すべての頂点で同じ次数を持ちます。

上の定理を証明するには、以下の補題を証明する必要があります。

補題
内周が $5$ で、最小次数 $r$ が $3$ 以上のムーアグラフの頂点 $u,v$
が辺で結ばれていないとき、$u,v$ の共通の近傍はちょうど1点である。

この補題はよく考えればわかりますから、省略します。


しかし、この性質が今後定理を証明するのに生きてきます。
また、$u,v$ が隣接しているとき、$u,v$ の共通の近傍は存在しませんので、
ムーアグラフの隣接行列 $A$ の2乗 $B$ を $B=(b_{ij})$ とするとき
$$b_{ij}=\begin{cases}r&i=j\\1&\{i,j\}\not\in E(G)\\0&\{i,j\}\in E(G)\end{cases}$$
が成り立ちます。ここで、$E(G)$ はグラフの辺の集合です。
ここで上の補題を使いました。

よって、
$$B=A^2=rI_n+J_n-I_n-A$$
が成り立ちます。
この関係式から、$r$ 以外の固有値 $\lambda$ は、$\lambda^2+\lambda-(r-1)=0$
を満たします。

つまり、固有値 $r$ の固有空間の次元は、1であり、
この2つの解とトレースゼロ条件とランクの式から、
$m_1\rho_1+m_2\rho_2+r=0$ かつ
$m_1+m_2+1=n=r^2+1$
となります。

これらの式から、$r=3,5,57$ しかないことがわかります。

$r=57$ の場合のデータをもう一度書いておくと、
頂点数 3250
最小次数 57
隣接行列の固有値は、$57$, $7$, $-8$
その重複度は $1$, $1729$, $1520$
となります。

Miniature 15
${\mathbb R}^d$ の中へのいくつかの点の埋め込みで、点同士の距離が
2種類のものを求めるとき、その頂点の最大値 $n(d)$ が $d$ によって
上から

$$n(d)\le \frac{1}{2}(d^2+5d+4)$$
による不等式が成り立つという内容です。