[場所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 件のコメント:
コメントを投稿