2
大学数学基礎解説
文献あり

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

241
0
$$$$

  1. フィッシャー不等式

  2. 算術三角形

  3. 自己同型群

  4. アフィン平面

    1. 相互直交ラテン方格


  5. シュタイナー三重系

    1. STSの直積


  6. マシュー群 $M_{11}$$M_{12}$

    1. S(2,3,9)の性質

    2. S(3,4,10)の構成

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

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

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

定理4-系1
$S(\Omega,\mathcal{B})$$S(2,k,v)$系, $|\mathcal{B}|=b$とすると,
\begin{eqnarray} v< b\Longrightarrow k^2\leq v \end{eqnarray}

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

定理4-系2
$S\coloneqq S(\Omega,\mathcal{B})$$S(2,k,v)$系とする. $|\mathcal{B}|=b$$v=b$を満たすとき, $S$$S(2,q+1,q^2+q+1)$の形で表せる.

とほぼ同様のため省略.

 $S(2,q+1,q^2+q+1)$の形をしたシュタイナーシステムのことを特に(有限)射影平面と呼び, $q$を位数という. 特にファノ平面$S(2,3,7)=S(2,2+1,2^2+2+1)$は位数が最小の射影平面である.

参考文献

[1]
R. C. Bose, A Note on Fisher's Inequality for Balanced Incomplete Block Designs, Annals of Mathematical Statistics, 1949, 619-620
投稿日:415
更新日:1日前
OptHub AI Competition

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。
バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

有限群論 好きな群は6次対称群

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中
  1. 定義
  2. 例. $S(2,3,7)$
  3. 基本的な性質
  4. フィッシャー不等式
  5. 参考文献