シュタイナーシステムとフィッシャー不等式

ブロックデザイン,組合せ論,シュタイナーシステム

241

フィッシャー不等式

算術三角形

自己同型群

アフィン平面
1. 相互直交ラテン方格

シュタイナー三重系
1. STSの直積

マシュー群 $M_{11}$と$M_{12}$

構成したシュタイナーシステム

(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})$であって, 条件

任意の$1\leq i\leq b$に対して, $|B_i|=k$
$\Omega$の任意の$t$元$\alpha_{p_1},\alpha_{p_2},\cdots,\alpha_{p_t}$を取ったとき, $\alpha_{p_1},\alpha_{p_2},\cdots,\alpha_{p_t}\in B_i$となる$B_i\in\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'$が存在することである.

例. $S(2,3,7)$

　$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元を取ってきても, それらをともに含むようなブロックが一意に存在していることを意味している.

構成法1.

　起点となる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}
と組み上げられる.

構成法2.

　$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)$を付け足せば同様の結果が得られる.

構成法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$の関係式を導く.

定理1

$S(t,k,v)$系$S(\Omega,\mathcal{B})$について, ある元$\alpha\in\Omega$を含むブロックの個数$r$は$\dfrac{\begin{pmatrix}v-1\\t-1\end{pmatrix}}{\begin{pmatrix}k-1\\t-1\end{pmatrix}}$.

$\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}}$.

上と同様.

定理2-系

$S(t,k,v)$系$S(\Omega,\mathcal{B})$について, ある元$\alpha\in\Omega$を含むブロックの個数を$r$, $\Omega$のある2元部分集合を含むブロックの個数を$\lambda_2$とすると,
\begin{eqnarray} r>\lambda_2 \end{eqnarray}

$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$の関係式を導く.

定理3

$S(t,k,v)$系$S(\Omega,\mathcal{B})$について, ある元を含むブロックの個数を$r$,$|\mathcal{B}|=b$とすると,
\begin{eqnarray} &&b=\frac{\begin{pmatrix}v\\t\end{pmatrix}}{\begin{pmatrix}k\\t\end{pmatrix}}=\frac{v(v-1)(v-2)\cdots(v-t+1)}{k(k-1)(k-2)\cdots(k-t+1)}\\ &&\iff bk=vr \end{eqnarray}

$\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}$である.

　接続行列を利用すれば, ブロックデザインの基礎的な関係式であるフィッシャー不等式を導出できる.

定理4　フィッシャー不等式

$S\coloneqq S(\Omega,\mathcal{B})$を$S(t,k,v)$系, ある元を含むブロックの個数を$r$,$|\mathcal{B}|=b$とすると,
\begin{eqnarray} v\leq b \end{eqnarray}
が成り立つ.

$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$.