外書輪講I(第7回)

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

HPに行く

今回は、Miniature 7,8,9

をやりました。

Miniature 7

は、続きですが、定理は以下のようになります。

定理

非負実数 $m_{ij}$ が、$m_{ij}=m_{ji}$ となるとき、

${\mathbb R}^n$ 上の $n+1$ 点 ${\bf p}_0,{\bf p}_1, \cdots, {\bf p}_n$ 

が、存在して、$||{\bf p}_i-{\bf p}_j||=m_{ij}$ となるための

必要充分条件は、$g_{ij}=\frac{1}{2}(m_{0i}+m_{0j}-m_{ij})$ となる

行列 $G=(g_{ij})$ が半正定値となることである。

これを証明してもらったのですが、内容はそれほど難しくありませんでした。
ただ、$A$ が半正定値であることと、
$A=X^TX$ となるような実正方行列 $X$ が存在することが
同値であることがまだ分からなかったようですので
その証明をもう一回やってもらうことになりました。

$n=2$ の場合に考えれば、この定理の条件は、
平面上の三角形の存在条件、つまり
それぞれの辺に関する三角不等式と同値になるはずです。

$$G=\begin{pmatrix}g_{11}&g_{12}\\g_{21}&g_{22}\end{pmatrix}$$
が半正定値でるあることは、この行列の固有値がどちらも非負であることですが、
これは、$\det(G)\ge 0$ かつ、$g_{11}\ge 0$ であることと同値となります。
(実対称行列の固有値はいつでも実数です。)
ここで、$g_{11}=m_{01}=||{\bf p}_0-{\bf p}_1||^2$ であるので、
この条件は $\det(G)\ge 0$ だけでよいことになります。
$\det(G)$ を計算します。
$m_{01}=x,m_{02}=y,m_{12}=z$ とすると、
$g_{11}=x^2$, $g_{12}=\frac{1}{2}(x^2+y^2-z^2)=g_{21}$, $g_{22}=y^2$
であるから、
$$\det(G)=x^2y^2-\frac{1}{4}(x^2+y^2-z^2)^2$$
$$=\frac{1}{4}(y+z-x)(x+y-z)(x-y+z)(x+y+z)$$
となります。
不等式 $\det(G)\ge 0$ であることと、
$y+z-x\ge 0$, $x+y-z\ge 0$, $x-y+z\ge 0$
は同値となります。
しかし、これは自明ではないので、これにもやはり証明が必要です。

Miniature 8

は、グラフ理論の話です。
完全グラフの辺を完全二部グラフの和によって

表すことに関する定理です。

まず、完全グラフ $K_n$ とは、頂点が $n$ 個のグラフで、
辺が最大のグラフをいいます。よって辺の数は $\binom{n}{2}$ となります。

二部グラフというのは、グラフで、頂点の集合が黒と白のどちらかの色がつけ、
そのグラフが黒同士、白同士には辺がないものを言います。

完全二部グラフとは、二部グラフで、辺が最大のものを言います。

グラフ $G$ がグラフの和によって表すということは、
$G$ の辺を互いに素な(共通部分を持たない)集合の和集合によって
$G=G_1\sqcup G_2\sqcup\cdots \sqcup G_n$
のように分解することとを表し、その辺の集合がグラフとなることをいいます。
この和は辺の分解を表し、頂点の集合は重なりがあってもよいです。

定理は、以下になります。

定理

もし、完全グラフ $K_n$ の辺が、部分完全二部グラフ $H_1,\cdots, H_m$

の和として、表せるとすると、$m\ge n-1$ が成り立つ。

例えば、$K_n$ の任意の辺に対して、その辺の両端の２個の頂点のみを
頂点とする完全二部グラフを作ることができます、
このとき、$\binom{n}{2}$ 個の部分完全二部グラフが作れるので、
$K_n$ には最大、$\binom{n}{2}$ 個の部分完全二部グラフの和として表され
ることが分かると思います。
このように、辺の分割を最大にするように部分二部グラフを作ることはすぐにできます。
しかし、どれほど小さい数の和として表されるかはすぐには分からない訳です。

この本では、$K_6$ に対して、5個の完全二部グラフの和によって
表す方法を示していますが、それより小さい完全二部グラフの和として
表されるかどうかはすぐにはわかりません。

実際、この定理は、そのような最小限界が $n-1$ だということを主張しているのです。

Miniature 9

は、Equiangular Linesの話題です。

等角直線の訳です。

原点を通る直線の族を考えます。この族は、

角度は何度でもよいが、とにかく、どの２つの直線もその

間の角度が等しくなるようにしたものをいいます。
問題は、${\mathbb R}^d$ 上に等角直線が何本引けるか？ということです。

示すのは、

定理

${\mathbb R}^d$ の原点を通る直線の族が

等角直線であるなら、その本数は、$\binom{d+1}{2}$ を大きくなることはない。

です。
たとえば、${\mathbb R}^3$ の中では、
正２０面体の対角線をとると、６本あり、この値は、
丁度定理の $\binom{d+1}{2}$ を与えています。
なので、$d=3$ ではこれ以上小さくはできないのですが、
$d\ge 4$ では、まだ、小さくすることもできるようです。

つまり、この定理では等角直線族の本数の上界を与えていますが、
その最大値を求める問題は非常に難しく、
一般にその値を与えることは未解決となっています。

ということで、この話題で何か研究することは、現代でもまだ続いているという
ことになります。

ある次元でも面白い直線の配置を求めることができれば面白い結果になるのでは
ないでしょうか？