[場所1E503（月曜日5限）]
現在外書輪講では、Matousekの33-Miniaturesをみんなで読んでいます。
今回は、Miniature -11, 12, 13をやりました。
Miniature-11
は行列の検算ついての話でした。
2つの $n\times n$ 行列を掛けるには、通常では $O(n^3)$ の手間がかかります。
その計算の確かめる確率的な方法があります。
この方法だと、$O(n^2)$ のオーダーくらいの手間です。
たとえば、${\bf x}\in \{0,1\}^n$ を適当に(確率$ 1/2^n$ )持ってくるとき、
$AB$ とその計算結果を $C$ としたとき、$AB{\bf x}$ と $C{\bf x}$ を
計算して、値が違えば、間違えているということがわかります。
この方法だと、ベクトルに行列を掛け算して得られる手間だけ、つまり
$O(n^2)$ の手間で検算ができることになります。
このMiniature の中に次の主張が含まれています。
$AB\neq C$ であるとき、この手法を使えば、少なくとも確率1/2で $AB\neq C$
を見出せる。
$D=C-AB$ として、$D$ がゼロ行列でないとします。
このとき、${\bf x}\in \{0,1\}^n$ を同確率で選ぶ時、
$D{\bf x}\neq 0$ となる確率は、少なくとも 1/2 であることを示せばよいです。
今、$D=(d_{kl})$ とし、${\bf y}=D{\bf x}$ とし
${\bf y}=(y_1,\cdots, y_n)^T$ とします。
$d_{kl}\neq 0$ とします。
このとき、$D{\bf x}=d_{k1}x_1+\cdots+d_{kn}$ とします。
今、$l=n$ としてもかまいません。
$y_n=d_{k1}x_1+\cdots+d_{kn}x_n=S+d_{kn}x_n$ とします。
$x_1,\cdots, x_{n-1}$ を固定して、$x_n$ を確率1/2で0か1を出すとします。
よって、$S$ は固定されており、$S$ か $S+d_{kn}$ のどちらかは $0$ ではないので、
そのどちらかで $y_n\neq 0$ が検出できます。
つまり、$D\neq 0$ が検出できます。
$x_1,\cdots, x_{n-1}$ が動いても同じ状況なので、
確率は少なくとも1/2で$y_n\neq 0$ かつ、${\bf y}\neq 0$ つまり、$D\neq O$ が検出できます。
Miniature 12
この話は、${\mathbb Q}$ 上のベクトル空間 ${\mathbb R}$ を用いることで、
定理
$x$ を無理数とします。$1,x$ を辺に持つ長方形 $R$ に対して、この長方形を
任意の有限個の正方形によって埋め尽くすことができない。
という内容です。ここで、有限個の正方形 $Q_1,Q_2,\cdots, Q_n$
によって埋め尽くすとは、
$R=Q_1,Q_2,\cdots, Q_n$ かつ、$i\neq j$ に対して、$Q_i\cap Q_j$ が、
$Q_i$, $Q_j$ の境界に含まれる。
ということを指します。
(証明)
有限個の正方形 $Q_1,Q_2,\cdots, Q_n$ によって $R$ を埋め尽くすとします。
$Q_i$ の辺の長さを $s_1,s_2,\cdots, s_n$ とします。
このとき、$V$ を $1,x,s_1.\cdots, s_n$ によって生成されれているベクトル空間
とします。
$x$ が無理数なので、$1,x$ は一次独立であり、
線形写像 $f:V\to {\mathbb R}$ で$f(1)=1$, $f(x)=-1$
を満たすものが存在します。
例えば、$b_1,b_2,\cdots, b_k$ を$V$ の基底とし、$b_1=1, b_2=x$ とすることができます。
$f(b_i)=0$, $i\ge 3$ とすればよいのです。
$s_1,s_2,\cdots, s_n$ は $1,x$ の ${\mathbb Q}$ 上の1次結合となる可能性は
あるので、改めて、$f(s_1)$ の行き先を自由に決めることはできるかどうかわかりません。
$s_1$ が有理数なら、$f(s_1)=s_1$ となります。
この写像を用いて、上の定理を示します。
$R$ を辺の長さが $a,b$ の長方形とします。
このとき、$v:\{\text{長方形}\}\to {\mathbb R}$ を
$v(R)\to f(a)f(b)$ と定義します。
このとき、
$v(R)=f(1)f(x)=-1=\sum_{i=1}^n(Q_i)=\sum_{i=1}^nf(s_i)^2\ge 0$
となり矛盾します。
ここで、示さなければならないのは、$Q_1,\cdots, Q_n$
が $R$ を埋め尽くしているとすると、$v(R)=\sum_{i=1}^n(Q_i)$ となることです。
Miniature 13
は、グラフ理論の話ですが、途中まででした。
内容は、以下となります。
定理
$K_{10}$ を頂点数 10 の完全グラフとします。
ペテルセングラフを $P$ とすると、$K_{10}$
を $P$ と同型な 3個の部分グラフによって覆うことができない。
ここで、グラフ $G$ がその部分グラフ $G_1,\cdots ,G_n$ で覆うとは、
$G_1,\cdots ,G_n$ が $G$ の部分グラフで、$G_1,\cdots,G_n$
の辺集合の和集合は、ちょうど $G$ の辺集合と一致します。
つまり、それらは、お互いに重複はありません。
ペテルセングラフについては、ここにリンクを貼っておきます。
リンクではピーターセンとなっていますが、どっちの発音が正しいのかは
知りません。
完全グラフ $K_n$ とは、どの2つの頂点も辺で結ばれるものをいいます。
頂点 $v$ に対して、$v$ に１つの辺でつながる頂点全体の集合を $v$ の
近傍といい、その個数を次数といいます。
$G$ が正則グラフとは、$G$ の各頂点の次数が一定のグラフのことをいいます。
また、$G$ の内周とは、$G$ に含まれる最小のサイクル(閉路)
の辺の数のことをいいます。
うえの定理を証明するのには、スペクトラルグラフ理論を用います。
スペクトラルグラフ理論で活躍するのは、隣接行列です。
隣接行列 $A=(a_{ij})$ を以下で定義します。
グラフ $G$ の頂点の個数を $n$ とし、$G$ の頂点に $1,2,\cdots, n$ の名前をつける。
$A$ は $n\times n$ 行列であって、
$$a_{ij}=\begin{cases}1&i,j\text{が辺で結ばれる}\\0&\text{上記以外}\end{cases}$$
としたものをいいます。
ペテルセングラフは頂点数が10で、次数が3の正則グラフです。
なので、ペテルセングラフの辺の数は、$10\times 3/2=15$ であり、
$K_{10}$ の辺の数は、$\binom{10}{2}=45$ すので、 ペテルセングラフで
$K_{10}$ を覆えるとすると、３つということになります。
次数が $r$ の正則グラフの隣接行列の固有値の絶対値の最大は
ちょうど $r$ ということが知られています。
現在外書輪講では、Matousekの33-Miniaturesをみんなで読んでいます。
今回は、Miniature -11, 12, 13をやりました。
Miniature-11
は行列の検算ついての話でした。
2つの $n\times n$ 行列を掛けるには、通常では $O(n^3)$ の手間がかかります。
その計算の確かめる確率的な方法があります。
この方法だと、$O(n^2)$ のオーダーくらいの手間です。
たとえば、${\bf x}\in \{0,1\}^n$ を適当に(確率$ 1/2^n$ )持ってくるとき、
$AB$ とその計算結果を $C$ としたとき、$AB{\bf x}$ と $C{\bf x}$ を
計算して、値が違えば、間違えているということがわかります。
この方法だと、ベクトルに行列を掛け算して得られる手間だけ、つまり
$O(n^2)$ の手間で検算ができることになります。
このMiniature の中に次の主張が含まれています。
$AB\neq C$ であるとき、この手法を使えば、少なくとも確率1/2で $AB\neq C$
を見出せる。
$D=C-AB$ として、$D$ がゼロ行列でないとします。
このとき、${\bf x}\in \{0,1\}^n$ を同確率で選ぶ時、
$D{\bf x}\neq 0$ となる確率は、少なくとも 1/2 であることを示せばよいです。
今、$D=(d_{kl})$ とし、${\bf y}=D{\bf x}$ とし
${\bf y}=(y_1,\cdots, y_n)^T$ とします。
このとき、$D{\bf x}=d_{k1}x_1+\cdots+d_{kn}$ とします。
今、$l=n$ としてもかまいません。
$y_n=d_{k1}x_1+\cdots+d_{kn}x_n=S+d_{kn}x_n$ とします。
$x_1,\cdots, x_{n-1}$ を固定して、$x_n$ を確率1/2で0か1を出すとします。
よって、$S$ は固定されており、$S$ か $S+d_{kn}$ のどちらかは $0$ ではないので、
そのどちらかで $y_n\neq 0$ が検出できます。
つまり、$D\neq 0$ が検出できます。
$x_1,\cdots, x_{n-1}$ が動いても同じ状況なので、
確率は少なくとも1/2で$y_n\neq 0$ かつ、${\bf y}\neq 0$ つまり、$D\neq O$ が検出できます。
Miniature 12
この話は、${\mathbb Q}$ 上のベクトル空間 ${\mathbb R}$ を用いることで、
次の幾何学的な定理を示します。
定理
$x$ を無理数とします。$1,x$ を辺に持つ長方形 $R$ に対して、この長方形を
任意の有限個の正方形によって埋め尽くすことができない。
という内容です。ここで、有限個の正方形 $Q_1,Q_2,\cdots, Q_n$
によって埋め尽くすとは、
$R=Q_1,Q_2,\cdots, Q_n$ かつ、$i\neq j$ に対して、$Q_i\cap Q_j$ が、
$Q_i$, $Q_j$ の境界に含まれる。
ということを指します。
(証明)
有限個の正方形 $Q_1,Q_2,\cdots, Q_n$ によって $R$ を埋め尽くすとします。
$Q_i$ の辺の長さを $s_1,s_2,\cdots, s_n$ とします。
このとき、$V$ を $1,x,s_1.\cdots, s_n$ によって生成されれているベクトル空間
とします。
$x$ が無理数なので、$1,x$ は一次独立であり、
線形写像 $f:V\to {\mathbb R}$ で$f(1)=1$, $f(x)=-1$
を満たすものが存在します。
例えば、$b_1,b_2,\cdots, b_k$ を$V$ の基底とし、$b_1=1, b_2=x$ とすることができます。
$f(b_i)=0$, $i\ge 3$ とすればよいのです。
$s_1,s_2,\cdots, s_n$ は $1,x$ の ${\mathbb Q}$ 上の1次結合となる可能性は
あるので、改めて、$f(s_1)$ の行き先を自由に決めることはできるかどうかわかりません。
$s_1$ が有理数なら、$f(s_1)=s_1$ となります。
この写像を用いて、上の定理を示します。
$R$ を辺の長さが $a,b$ の長方形とします。
このとき、$v:\{\text{長方形}\}\to {\mathbb R}$ を
$v(R)\to f(a)f(b)$ と定義します。
このとき、
$v(R)=f(1)f(x)=-1=\sum_{i=1}^n(Q_i)=\sum_{i=1}^nf(s_i)^2\ge 0$
となり矛盾します。
ここで、示さなければならないのは、$Q_1,\cdots, Q_n$
が $R$ を埋め尽くしているとすると、$v(R)=\sum_{i=1}^n(Q_i)$ となることです。
Miniature 13
は、グラフ理論の話ですが、途中まででした。
内容は、以下となります。
定理
$K_{10}$ を頂点数 10 の完全グラフとします。
ペテルセングラフを $P$ とすると、$K_{10}$
を $P$ と同型な 3個の部分グラフによって覆うことができない。
ここで、グラフ $G$ がその部分グラフ $G_1,\cdots ,G_n$ で覆うとは、
$G_1,\cdots ,G_n$ が $G$ の部分グラフで、$G_1,\cdots,G_n$
の辺集合の和集合は、ちょうど $G$ の辺集合と一致します。
つまり、それらは、お互いに重複はありません。
ペテルセングラフについては、ここにリンクを貼っておきます。
リンクではピーターセンとなっていますが、どっちの発音が正しいのかは
知りません。
完全グラフ $K_n$ とは、どの2つの頂点も辺で結ばれるものをいいます。
頂点 $v$ に対して、$v$ に１つの辺でつながる頂点全体の集合を $v$ の
近傍といい、その個数を次数といいます。
$G$ が正則グラフとは、$G$ の各頂点の次数が一定のグラフのことをいいます。
また、$G$ の内周とは、$G$ に含まれる最小のサイクル(閉路)
の辺の数のことをいいます。
うえの定理を証明するのには、スペクトラルグラフ理論を用います。
スペクトラルグラフ理論で活躍するのは、隣接行列です。
隣接行列 $A=(a_{ij})$ を以下で定義します。
グラフ $G$ の頂点の個数を $n$ とし、$G$ の頂点に $1,2,\cdots, n$ の名前をつける。
$A$ は $n\times n$ 行列であって、
$$a_{ij}=\begin{cases}1&i,j\text{が辺で結ばれる}\\0&\text{上記以外}\end{cases}$$
としたものをいいます。
ペテルセングラフは頂点数が10で、次数が3の正則グラフです。
なので、ペテルセングラフの辺の数は、$10\times 3/2=15$ であり、
$K_{10}$ の辺の数は、$\binom{10}{2}=45$ すので、 ペテルセングラフで
$K_{10}$ を覆えるとすると、３つということになります。
次数が $r$ の正則グラフの隣接行列の固有値の絶対値の最大は
ちょうど $r$ ということが知られています。
0 件のコメント:
コメントを投稿