構成したシュタイナーシステム
(2,3,7)NEW
本筋から逸れる証明は折畳んでいる場合があるが, クリックで開くことができる.
$v$点集合$\Omega=\lbrace\alpha_1,\alpha_2,\cdots,\alpha_v\rbrace$とその部分集合族$\mathcal{B}=\lbrace B_1,B_2,\cdots,B_b\rbrace$の組$(\Omega,\mathcal{B})$であって, 条件
を満たすものをシュタイナーシステムまたはシュタイナー系と呼び, $S(t,k,v)=S(\Omega,\mathcal{B})$のように表記する.
$\mathcal{B}$の元をブロックといい, 以降$0< t< k< v$を仮定する.
すぐに明らかになることだが, シュタイナーシステムに関するいくつかのパラメータは$t,k,v$によって表されるため, この3組を明示する.
$S(\Omega,\mathcal{B})$という表記は特定の集合とその部分集合族の組がシュタイナーシステムの要件を満たしているということを表しており, $S(t,k,v)$という表記は, シュタイナーシステムが群などと同様, $t,k,v$によって定まるような, ある構造に従う無限系列であることを表している. そのため, 構造自体に着目したい場合は$S(t,k,v)$系$S(\Omega,\mathcal{B})$などと表記することがある.
2つの$S(t,k,v)$系$T=S(\Omega,\mathcal{B})$と$T'=S(\Omega',\mathcal{B}')$が同型であるとは,
\begin{eqnarray}
(\alpha_1,\alpha_2,\cdots,\alpha_k)\in\mathcal{B}\iff(f(\alpha_1),f(\alpha_2),\cdots,f(\alpha_k))\in\mathcal{B}'
\end{eqnarray}
を満たす全単射$f\colon\Omega\longrightarrow\Omega'$が存在することである.
$F=S(\Omega,\mathcal{B})=S(2,3,7)$を構成する. 定義によると, $S(2,3,7)$とは$7$点集合$\Omega=\lbrace1,2,3,4,5,6,7\rbrace$と長さ$3$の部分集合族の組であって, どのような$\Omega$の2元を取ってきても, それらをともに含むようなブロックが一意に存在していることを意味している.
起点となる3つ組を$(1,2,3)$とする. $(1,n)$の組を網羅するために, $(1,4,7)$と$(1,5,6)$を取る. 次に$(2,n)$の組を入れるために, $4,5,6,7$の組み合わせが重複しないように$(2,4,6),(2,5,7)$を取る. 同様にして$(3,4,5),(3,6,7)$を取れば,
\begin{eqnarray}
\mathcal{B}=\lbrace(1,2,3),(1,4,7),(1,5,6),(2,4,6),(2,5,7),(3,4,5),(3,6,7)\rbrace
\end{eqnarray}
と組み上げられる.
$4,5,6,7$を2つの組に分ける方法は$\lbrace(4,7),(5,6)\rbrace,\hspace{3mm}\lbrace(4,6),(5,7)\rbrace,\hspace{3mm}\lbrace(4,5),(6,7)\rbrace$の3通り.
\begin{eqnarray}
\begin{array}{|cc|}\hline
\cellcolor{#585858}\textcolor{white}{4}&\cellcolor{#585858}\textcolor{white}{7}\\
6&5\\\hline
\end{array}\hspace{2mm}\begin{array}{|cc|}\hline
\cellcolor{#585858}\textcolor{white}{4}&7\\
\cellcolor{#585858}\textcolor{white}{6}&5\\\hline
\end{array}\hspace{2mm}\begin{array}{|cc|}\hline
\cellcolor{#585858}\textcolor{white}{4}&7\\
6&\cellcolor{#585858}\textcolor{white}{5}\\\hline
\end{array}\hspace{2mm}
\end{eqnarray}
各々を$1,2,3$と組み合わせれば,
$(1,4,7),(1,5,6)$
$(2,4,6),(2,5,7)$
$(3,4,5),(3,6,7)$
\begin{eqnarray}
\begin{array}{|cc|}\hline
&\cellcolor{#585858}\textcolor{white}{1}\\
2&3\\
\cellcolor{#585858}\textcolor{white}{4}&\cellcolor{#585858}\textcolor{white}{7}\\
6&5\\\hline
\end{array}\hspace{2mm}\begin{array}{|cc|}\hline
&\cellcolor{#585858}\textcolor{white}{1}\\
2&3\\
4&7\\
\cellcolor{#585858}\textcolor{white}{6}&\cellcolor{#585858}\textcolor{white}{5}\\\hline
\end{array}\hspace{2mm}\begin{array}{|cc|}\hline
&1\\
\cellcolor{#585858}\textcolor{white}{2}&3\\
\cellcolor{#585858}\textcolor{white}{4}&7\\
\cellcolor{#585858}\textcolor{white}{6}&5\\\hline
\end{array}\hspace{2mm}\begin{array}{|cc|}\hline
&1\\
\cellcolor{#585858}\textcolor{white}{2}&3\\
4&\cellcolor{#585858}\textcolor{white}{7}\\
6&\cellcolor{#585858}\textcolor{white}{5}\\\hline
\end{array}\hspace{2mm}\begin{array}{|cc|}\hline
&1\\
2&\cellcolor{#585858}\textcolor{white}{3}\\
\cellcolor{#585858}\textcolor{white}{4}&7\\
6&\cellcolor{#585858}\textcolor{white}{5}\\\hline
\end{array}\hspace{2mm}\begin{array}{|cc|}\hline
&1\\
2&\cellcolor{#585858}\textcolor{white}{3}\\
4&\cellcolor{#585858}\textcolor{white}{7}\\
\cellcolor{#585858}\textcolor{white}{6}&5\\\hline
\end{array}\hspace{2mm}
\end{eqnarray}
となり, 最後に$(1,2,3)$を付け足せば同様の結果が得られる.
$S(2,3,7)$の場合, ファノ平面と呼ばれる図形で可視化ができる.
線分も円も広義での直線と捉えれば, 直線がブロックを成していて, シュタイナーシステムの定義も満足していることが確認できる.
\begin{eqnarray}
\mathcal{B}=\lbrace(1,2,3),(1,4,7),(1,5,6),(2,4,6),(2,5,7),(3,4,5),(3,6,7)\rbrace
\end{eqnarray}
一般のシュタイナーシステムの性質をいくつか見た後, ブロックの個数$b$と$t,k,v$の関係式を導く.
$\Omega$において, $\alpha$を含むような$t$元の選び方は$\begin{pmatrix}v-1\\t-1\end{pmatrix}$通り.
$\mathcal{B}$において, $\alpha$を含むブロックとして$B_i$を取る. $B_i$の$k$個の元から$\alpha$を含むような$t$元の選び方は$\begin{pmatrix}k-1\\t-1\end{pmatrix}$通り. いま, $\alpha$を含むブロックの個数を$r$としているのだから, $\alpha$を含む$t$元の選び方は$r\begin{pmatrix}k-1\\t-1\end{pmatrix}$通り.
したがって,
\begin{eqnarray}
r\begin{pmatrix}k-1\\t-1\end{pmatrix}&=&\begin{pmatrix}k-1\\t-1\end{pmatrix}\\
\iff r&=&\frac{\begin{pmatrix}v-1\\t-1\end{pmatrix}}{\begin{pmatrix}k-1\\t-1\end{pmatrix}}
\end{eqnarray}
これは以下のように一般化できる.
$S(\Omega,\mathcal{B})$を$S(t,k,v)$系とする. $1\leq i\leq t$として, $\Omega$のある$i$元部分集合を含むブロックの個数$\lambda_i$は$\dfrac{\begin{pmatrix}v-i\\t-i\end{pmatrix}}{\begin{pmatrix}k-i\\t-i\end{pmatrix}}$.
上と同様.
$k< v$を仮定していたのだから,$\dfrac{v-1}{k-1}>1$.
辺々$\dfrac{(v-2)(v-3)\cdots(v-t+1)}{(k-2)(k-3)\cdots(k-t+1)}>0$を掛けて,
\begin{eqnarray}
r&=&\frac{v-1}{k-1}\cdot\frac{(v-2)(v-3)\cdots(v-t+1)}{(k-2)(k-3)\cdots(k-t+1)}\\
&>&\frac{(v-2)(v-3)\cdots(v-t+1)}{(k-2)(k-3)\cdots(k-t+1)}\\
&=&\lambda_2
\end{eqnarray}
ブロックの個数$b$と$t,k,v$の関係式を導く.
$\alpha\in\Omega,B\in\mathcal{B}$として, $\alpha\in B$を満たすような組$(\alpha,B)$の個数$m$を2通りの方法で求める.
[i] ブロックの選び方は$b$通り. ブロックの大きさは$k$であるから, 選んだブロックに含まれている元の選び方は$k$通り.
したがって, $m=bk$.
[ii] $\Omega$の元の選び方は$v$通り. ある元を含むブロックの個数を$r$としたため, $m=vr$.
以上より,$bk=vr$.
$r=\dfrac{(v-1)(v-2)\cdots(v-t+1)}{(k-1)(k-2)\cdots(k-t+1)}$から,
\begin{eqnarray}
b&=&\frac{vr}{k}\\
&=&\frac{v(v-1)(v-2)\cdots(v-t+1)}{k(k-1)(k-2)\cdots(k-t+1)}\\
&=&\frac{\begin{pmatrix}v\\t\end{pmatrix}}{\begin{pmatrix}k\\t\end{pmatrix}}
\end{eqnarray}
準備として, シュタイナーシステムの接続行列を導入する.
$\Omega=\lbrace\alpha_1,\alpha_2,\cdots,\alpha_v\rbrace,\mathcal{B}=\lbrace B_1,B_2,\cdots,B_b\rbrace$, $S\coloneqq S(\Omega,\mathcal{B})$を$S(t,k,v)$系とする. $S$の接続行列とは, 各成分が
\begin{eqnarray}
a_{ij}=\left\{\begin{array}{ll}
1 & \alpha_i\in B_j\hspace{2mm}(1\leq i\leq v,1\leq j\leq b)\\
0 & {\rm otherwise}
\end{array}\right.\end{eqnarray}
によって定義された行列$A=\begin{bmatrix}a_{ij}\end{bmatrix}$である.
接続行列を利用すれば, ブロックデザインの基礎的な関係式であるフィッシャー不等式を導出できる.
$S$の接続行列を$A$, $\Omega$のある2元部分集合を含むブロックの個数を$\lambda_2$として, $v$次正方行列$AA^\top=\begin{bmatrix}b_{ij}\end{bmatrix}$を考える.
$AA^\top$は, $A$の行同士の内積を取っていると捉えられるため,
\begin{eqnarray}
b_{ij}=\left\{\begin{array}{ll}
r & i=j\\
\lambda_2 & i\neq j
\end{array}\right.\end{eqnarray}
と書ける.
$AA^\top$の行列式に関して,
\begin{eqnarray}
\det AA^\top&=&\begin{vmatrix}r&\lambda_2&\cdots&\lambda_2\\\lambda_2&r&\cdots&\lambda_2\\\vdots&\vdots&\ddots&\vdots\\\lambda_2&\lambda_2&\cdots&r\end{vmatrix}\\
&=&\begin{vmatrix}r+(v-1)\lambda_2&r+(v-1)\lambda_2&\cdots&r+(v-1)\lambda_2\\\lambda_2&r&\cdots&\lambda_2\\\vdots&\vdots&\ddots&\vdots\\\lambda_2&\lambda_2&\cdots&r\end{vmatrix}\\
&=&\begin{vmatrix}r+(v-1)\lambda_2&0&\cdots&0\\\lambda_2&r-\lambda_2&\cdots&0\\\vdots&\vdots&\ddots&\vdots\\\lambda_2&0&\cdots&r-\lambda_2\end{vmatrix}\\
&=&(r-\lambda_2)^{v-1}(r+(v-1)\lambda_2)
\end{eqnarray}
$r>\lambda_2$から
\begin{eqnarray}
r-\lambda_2&\neq&0\\
r+(v-1)\lambda_2=r-\lambda_2+v\lambda_2&\neq&0
\end{eqnarray}
よって,
\begin{eqnarray}
\det AA^\top&\neq&0\\
\iff \rank AA^\top&=&v
\end{eqnarray}
行列の階数は積によって広義に減少することから$v=\rank AA^\top\leq\rank A$.
一方, $A$は$v\times b$行列であるため, $\rank A\leq b$.
以上より$v\leq b$.
$bk=vr$から
\begin{eqnarray}
v&<&b\\
vk&<&bk=vr\\
k&<&r\\
k+1&\leq&r=\frac{v-1}{k-1}\\
k^2&\leq&v
\end{eqnarray}
上とほぼ同様のため省略.
$S(2,q+1,q^2+q+1)$の形をしたシュタイナーシステムのことを特に(有限)射影平面と呼び, $q$を位数という. 特にファノ平面$S(2,3,7)=S(2,2+1,2^2+2+1)$は位数が最小の射影平面である.