数学外書輪講I(第15回)

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

HPに行く

このページは7/29に行われた授業に基づいています。

完全グラフを完全二部グラフによって分割すること

についてやりました。

前々回(こちら)も同じ定理について証明してもらいましたが、

今回はマトウセクに書かれている線形代数を用いた方法です。

定理をもう一度書いておくと、次のようになります。

定理

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

によって分割することができるなら、$m\ge n-1$ である。

完全二部グラフによって分割できるとは、

完全グラフ $K_n$ の頂点と辺を用いて完全二部グラフ $H_j$ を

$m$ 個つくったとき、$K_n$ の辺の集合が、$H_1,\cdots, H_m$ の

辺の集合によってちょうど分割されるということになります。

つまり、$H_1,H_2,\cdots, H_m$ のそれぞれの辺の数の和は、ちょうど

${}_nC_2=n(n-1)/2$ 個ということになります。

$H_j$ の頂点の集合を $V(H_j)=X_j\sqcup Y_j$ とします。

いま、$n\times n$ 行列 $A_k=(a_{ij}^{(k)})$ を

$$a_{ij}^{(k)}=\begin{cases}1&i\in X_k\text{かつ}j\in Y_k\\0&otherwise\end{cases}$$

とします。

すると、$\text{rank}(A_k)=1$ であることはすぐわかります。

$A=\sum_{k=1}^mA_k$ とすると、

また、$A+A^t=J_n-I_n$ が成り立ちます。

ここで、$I_n$ は $n\times n$ 単位行列で、$J_n$ は $n\times n$ 行列で、

すべての成分が $1$ となる行列とします。

ここで、$\text{rank}(A)\le \sum_{i=1}^m\text{rank}(A_i)=m$

であり、$n-1\le \text{rank}(A)$ であることを示せればよいです。

$\text{rank}(A)\le n-2$ であるとします。
${\bf 1}$ をすべて $1$ からなる横ベクトルとします。
すると、$\begin{pmatrix}A\\{\bf 1}\end{pmatrix}$ のランクは $n-1$ 以下であるから、

このとき、${\bf x}\in {\mathbb R}^n$ が存在して、

$A{\bf x}={\bf 1}\cdot {\bf x}={\bf 0}$ かつ ${\bf x}\neq {\bf 0}$ となります。

このベクトル ${\bf x}$ を用いて、
$${\bf x}^t(A+A^t){\bf x}={\bf x}^t(J_n-I_n){\bf x}={\bf x}^tJ_n{\bf x}-{\bf x}^t\cdot {\bf x}=-{\bf x}^t\cdot {\bf x}<0$$
かつ、
$${\bf x}^t(A+A^t){\bf x}={\bf x}^tA{\bf x}+{\bf x}^tA^t{\bf x}={\bf x}^t\cdot {\bf 0}+{\bf 0}^t\cdot {\bf x}=0$$
となり、矛盾します。

背理法から、$n-1\le \text{rank}(A)$ であることがわかります。

よって、$n-1\le m$ であることがわかります。