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

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

HPに行く

この内容は、7/19に行った外書輪講での授業に基づいています。

長方形を正方形で覆うこと

これは、マトウセクのMiniature 12に関する内容です。

内容は以下の定理についてです。

定理

辺の長さが $1$ と $x$ である長方形 $R$ を考えます。

ここで、$x$ はある無理数です。

このとき、内部を共有しない有限個の長方形によって

$R$ を覆うことはできない。

というものです。

この証明を線形代数を用いて行いました。

(証明)

もし、正方形 $Q_1,\cdots, Q_n$ によって、$R$ が覆えたとします。

ここで、$s_i$ を $Q_i$ の1辺の長さとします。

ここで、$\mathbb R$ は ${\mathbb Q}$ 係数の

ベクトル空間であることを用います。

特に、$1$ と $\alpha$ が1次独立であることと、$\alpha$ が

無理数であることは同値です。

$V\subset {\mathbb R}$ を $1, x,s_1,\cdots, s_n$  によって

生成されるベクトル空間とします。

今、

$f:V\to {\mathbb R}$ を

$f(1)=1$ かつ、$f(x)=-1$ となる線形写像とします。

そのような写像は、$b_1,\cdots, b_k$ を $V$ の基底として、

$b_1=1, b_2=x$ として取ることができます。

そのとき、$f(b_1)=1, f(b_2)=-1$ かつ、$f(b_i)=0$ $(i\ge 2)$

として取ればよく、取り方に矛盾しません。

今、2辺が $a,b$ となる長方形 $A$ に対して、$v(A)=f(a)f(b)\in {\mathbb R}$

を割り当てる関数 $v$ を考えます。

そのとき、簡単な考察から、

$v(R)=\sum_{i=1}^nv(Q_i)$ が成り立ちます。

よって、

$v(Q_i)=f(s_i)^2\ge 0$ となり、右辺は非負実数であるのに対して、

左辺は、

$v(R)=f(1)f(x)=-1$ であり、負の数となり、

矛盾します。

よって、$R$ は有限この

正方形で覆えないということになりました。

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

ある集合 $X$ を交わりのない2つの

集合 $A,B$ によって $X=A\sqcup B$ のように分割しておきます。

このとき、二部グラフというのは、$X$ 上のグラフで、

辺集合は必ず $A$ と $B$ の点を結んでいるものをいいます。

完全二部グラフというのは二部グラフとして考えられうる辺を

重複した辺を持たずに全て結んだ二部グラフのことを言います。

また、完全グラフは、グラフとして全ての頂点に対して

全ての頂点の組み合わせに対して、1つずつ辺を結んで

できるグラフのことです。

このとき、以下の定理が成り立ちます。

定理

もし、完全グラフ $K_n$ がある部分完全二部グラフ

$H_1,\cdots ,H_m$ によって分割したとき、

$m\ge n-1$ を満たす。

部分グラフ $H_i$ とは$K_n$ の頂点の部分集合を頂点集合とし、

$K_n$ の辺集合の部分集合を辺とするグラフのことを言います。

$H_i$ の二部グラフとしての分割 $A\sqcup B$ は適当に

決めるとします。

ここで分割とは、$K_n$ の辺を $H_1,\cdots ,H_m$ の辺で

全てひとつずつ覆うことを意味します。

なので、$H_1,\cdots, H_m$ の中で、頂点が重複していても構いません。

この証明として線形代数を用いる方法がありますが、

ここでは、多項式を用いた、Proofs from THE BOOK

に載っている、Tverberg の証明をします。

(証明)

$K_n$ が $H_1,\cdots, H_m$ のような完全二部グラフによって

分割できたとします。

ここで、$H_j$ の2つの頂点の集合を $L_j,R_j$ とします。

辺集合による分割に従って、以下の式を成立させることができます。

$$\sum_{i<j}x_ix_j=\sum_{k=1}^m(\sum_{a\in L_k}x_a\sum_{b\in R_k}x_b)$$

今、$m<n-1$ とすると、この等式が成り立たないことを示します。

ここで、$x_1+\cdots +x_n=0$ かつ $\sum_{a\in L_k}a_x=0$

を満たす$x_1,\cdots, x_n$ を考えます。

これは $m+1$ 個の線形な方程式だから、

ある $c_1,\cdots, c_n\in {\mathbb R}$ で、全て $0$ ではないような解が存在します。

そのような、$c_1,\cdots, c_n$ を取ってやると、$\sum_{i<j}c_ic_j=0$

が成り立つことがわかります。

しかし、

$$0=(c_1+\cdots+c_n)^2=\sum_{i=1}^nc_i^2+2\sum_{i<j}c_ic_j=\sum_{i=1}^nc_i^2>0$$

であることから、

矛盾します。

故に、$m\ge n-1$ であることがわかりました。