Steinerシステム - Fisher不等式
- Fisher不等式
- 自己同型群
- アフィン平面
-
Steinerトリプルシステム
- Mathieu群 $M_{11}$と$M_{12}$
構成したSteinerシステム
(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}$が存在して一意
を満たすものをSteinerシステムと呼び, $S(t,k,v)=S(\Omega,\mathcal{B})$のように表記する.
$\mathcal{B}$の元をブロックといい, 以下では$0< t< k< v$を仮定する.
すぐに明らかになることだが, Steinerシステムに関するいくつかのパラメータは$t,k,v$によって表されるため, この3組を明示する.
例
定義に従って$F=S(\Omega,\mathcal{B})=S(2,3,7)$を構成する.
構成法1.
$\Omega=\lbrace 1,2,3,4,5,6,7\rbrace$として, 起点となる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通り.
各々を$1,2,3$と組み合わせれば,
$(1,4,7),(1,5,6)$
$(2,4,6),(2,5,7)$
$(3,4,5),(3,6,7)$
となり, 最後に$(1,2,3)$を付け足せば同様の結果が得られる.
構成法3.
$S(2,3,7)$の場合, Fano平面と呼ばれる図形で可視化ができる.
線分も円も広義での直線と捉えれば, 直線がブロックを成していて, Steinerシステムの定義も満足していることが確認できる.
\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}
基本的な性質
一般のSteinerシステムの性質をいくつか見た後, ブロックの個数$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=S(t,k,v)=S(\Omega,\mathcal{B})$をSteinerシステムとする. $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}}$.
定理1と同様.
$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$を求める.
[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}
Fisher不等式
Steinerシステムの接続行列を導入する.
$\Omega=\lbrace\alpha_1,\alpha_2,\cdots,\alpha_v\rbrace,\mathcal{B}=\lbrace B_1,B_2,\cdots,B_b\rbrace$で$S=S(t,k,v)=S(\Omega,\mathcal{B})$をSteinerシステムとする. $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}$である.
接続行列を利用すれば, ブロックデザインの基礎的な関係式であるFisher不等式を導出できる.
$S$の接続行列を$A$, $\Omega$のある元を含むブロックの個数を$r$, ある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}
{\rm 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}
{\rm det}(AA^\top)&\neq&0\\
\iff {\rm rank}(AA^\top)&=&v
\end{eqnarray}
行列の階数は積によって広義に減少することから$v={\rm rank}(AA^\top)\leq{\rm rank}A$.
一方, $A$は$v\times b$行列であるため, ${\rm 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)$の形をしたSteinerシステムのことを特に(有限)射影平面と呼び, $q$を位数という. Fano平面$S(2,3,7)$は位数が最小の射影平面である.
