大学数学基礎解説

文献あり

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

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

184

Fisher不等式

自己同型群

アフィン平面

Steinerトリプルシステム
1. STSの直積

Mathieu群 $M_{11}$ と $M_{12}$
1. S(2,3,9)の性質
2. S(3,4,10)の構成

構成したSteinerシステム

(2,3,7)NEW

定義

Steinerシステム

$v$ 点集合 $Ω = {α_{1}, α_{2}, \dots, α_{v}}$ とその部分集合族 $B = {B_{1}, B_{2}, \dots, B_{b}}$ の組 $(Ω, B)$ であって, 条件

任意の $1 \leq i \leq b$ に対して, $| B_{i} | = k$
$Ω$ の任意の $t$ 元 $α_{p_{1}}, α_{p_{2}}, \dots, α_{p_{t}}$ を取ったとき, $α_{p_{1}}, α_{p_{2}}, \dots, α_{p_{t}} \in B_{i}$ となる $B_{i} \in B$ が存在して一意

を満たすものをSteinerシステムと呼び, $S (t, k, v) = S (Ω, B)$ のように表記する.
$B$ の元をブロックといい, 以下では $0 < t < k < v$ を仮定する.

　すぐに明らかになることだが, Steinerシステムに関するいくつかのパラメータは $t, k, v$ によって表されるため, この3組を明示する.

例

　定義に従って $F = S (Ω, B) = S (2, 3, 7)$ を構成する.

構成法1.

　 $Ω = {1, 2, 3, 4, 5, 6, 7}$ として, 起点となる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{array}{r} B = {(1, 2, 3), (1, 4, 7), (1, 5, 6), (2, 4, 6), (2, 5, 7), (3, 4, 5), (3, 6, 7)} \end{array}$
と組み上げられる.

構成法2.

　 $4, 5, 6, 7$ を2つの組に分ける方法は ${(4, 7), (5, 6)}, {(4, 6), (5, 7)}, {(4, 5), (6, 7)}$ の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{array}{r} B = {(1, 2, 3), (1, 4, 7), (1, 5, 6), (2, 4, 6), (2, 5, 7), (3, 4, 5), (3, 6, 7)} \end{array}$

基本的な性質

　一般のSteinerシステムの性質をいくつか見た後, ブロックの個数 $b$ と $t, k, v$ の関係式を導く.

定理1

S = S (t, k, v) = S (Ω, B)

をSteinerシステムとする. ある元

α \in Ω

を含むブロックの個数

r

は

\frac{(\begin{matrix} v - 1 \\ t - 1 \end{matrix})}{(\begin{matrix} k - 1 \\ t - 1 \end{matrix})}

である.

$Ω$ において, $α$ を含むような $t$ 元の選び方は $(\begin{matrix} v - 1 \\ t - 1 \end{matrix})$ 通り.
$B$ において, $α$ を含むブロックとして $B_{i}$ を取る. $B_{i}$ の $k$ 個の元から $α$ を含むような $t$ 元の選び方は $(\begin{matrix} k - 1 \\ t - 1 \end{matrix})$ 通り.
いま, $α$ を含むブロックの個数を $r$ としているのだから, $α$ を含む $t$ 元の選び方は $r (\begin{matrix} k - 1 \\ t - 1 \end{matrix})$ 通り.
したがって,
$\begin{array}{rcl} r (\begin{array}{c} k - 1 \\ t - 1 \end{array}) & = & (\begin{array}{c} k - 1 \\ t - 1 \end{array}) \\ ⟺ r & = & \frac{(\begin{array}{c} v - 1 \\ t - 1 \end{array})}{(\begin{array}{c} k - 1 \\ t - 1 \end{array})} \end{array}$

　これは以下のように一般化できる.

$S = S (t, k, v) = S (Ω, B)$ をSteinerシステムとする. $1 \leq i \leq t$ として, $Ω$ のある $i$ 元部分集合を含むブロックの個数 $λ_{i}$ は $\frac{(\begin{matrix} v - i \\ t - i \end{matrix})}{(\begin{matrix} k - i \\ t - i \end{matrix})}$ .

定理1と同様.

定理2-系

S = S (t, k, v) = S (Ω, B)

をSteinerシステムとする. ある元

α \in Ω

を含むブロックの個数を

r

Ω

のある2元部分集合を含むブロックの個数を

λ_{2}

とすると,

\begin{array}{r} r > λ_{2} \end{array}

$k < v$ を仮定していたのだから, $\frac{v - 1}{k - 1} > 1$ .
辺々 $\frac{(v - 2) (v - 3) \dots (v - t + 1)}{(k - 2) (k - 3) \dots (k - t + 1)} > 0$ を掛けて,
$\begin{array}{rcl} r & = & \frac{v - 1}{k - 1} \cdot \frac{(v - 2) (v - 3) \dots (v - t + 1)}{(k - 2) (k - 3) \dots (k - t + 1)} \\ > & \frac{(v - 2) (v - 3) \dots (v - t + 1)}{(k - 2) (k - 3) \dots (k - t + 1)} \\ = & λ_{2} \end{array}$

　ブロックの個数 $b$ と $t, k, v$ の関係式を導く.

定理3

S = S (t, k, v) = S (Ω, B)

をSteinerシステムとする. ある元を含むブロックの個数を

r

| B | = b

とすると,

\begin{array}{rcl} b = \frac{(\begin{array}{c} v \\ t \end{array})}{(\begin{array}{c} k \\ t \end{array})} = \frac{v (v - 1) (v - 2) \dots (v - t + 1)}{k (k - 1) (k - 2) \dots (k - t + 1)} \\ ⟺ b k = v r \end{array}

$α \in Ω, B \in B$ として, $α \in B$ を満たすような組 $(α, B)$ の個数 $m$ を求める.
[i] ブロックの選び方は $b$ 通り. ブロックの位数は $k$ であるから, 選んだブロックに含まれている元の選び方は $k$ 通り.
したがって, $m = b k$ .
[ii] $Ω$ の元の選び方は $v$ 通り. ある元を含むブロックの個数を $r$ としたため, $m = v r$ .
以上より, $b k = v r$ .
$r = \frac{(v - 1) (v - 2) \dots (v - t + 1)}{(k - 1) (k - 2) \dots (k - t + 1)}$ から,
$\begin{array}{rcl} b & = & \frac{v r}{k} \\ = & \frac{v (v - 1) (v - 2) \dots (v - t + 1)}{k (k - 1) (k - 2) \dots (k - t + 1)} \\ = & \frac{(\begin{array}{c} v \\ t \end{array})}{(\begin{array}{c} k \\ t \end{array})} \end{array}$

Fisher不等式

　Steinerシステムの接続行列を導入する.

接続行列

$Ω = {α_{1}, α_{2}, \dots, α_{v}}, B = {B_{1}, B_{2}, \dots, B_{b}}$ で $S = S (t, k, v) = S (Ω, B)$ をSteinerシステムとする. $S$ の接続行列とは, 各成分が
$\begin{array}{r} a_{i j} = {\begin{cases} 1 & α_{i} \in B_{j} (1 \leq i \leq v, 1 \leq j \leq b) \\ 0 & o t h e r w i s e \end{cases} \end{array}$
によって定義された行列 $A = [\begin{matrix} a_{i j} \end{matrix}]$ である.

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

Fisher不等式

S = S (t, k, v) = S (Ω, B)

をSteinerシステムとする. ある元を含むブロックの個数を

r

| B | = b

とすると,

\begin{array}{r} v \leq b \end{array}

が成り立つ.

$S$ の接続行列を $A$ , $Ω$ のある元を含むブロックの個数を $r$ , ある2元部分集合を含むブロックの個数を $λ_{2}$ として, $v$ 次正方行列 $A A^{⊤} = [\begin{matrix} b_{i j} \end{matrix}]$ を考える.
$A A^{⊤}$ は, $A$ の行同士の内積を取っていると捉えられるため,
$\begin{array}{r} b_{i j} = {\begin{cases} r & i = j \\ λ_{2} & i \neq j \end{cases} \end{array}$
と書ける.
$A A^{⊤}$ の行列式に関して,
$\begin{array}{rcl} d e t (A A^{⊤}) & = & | \begin{array}{c} r & λ_{2} & \dots & λ_{2} \\ λ_{2} & r & \dots & λ_{2} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ λ_{2} & λ_{2} & \dots & r \end{array} | \\ = & | \begin{array}{c} r + (v - 1) λ_{2} & r + (v - 1) λ_{2} & \dots & r + (v - 1) λ_{2} \\ λ_{2} & r & \dots & λ_{2} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ λ_{2} & λ_{2} & \dots & r \end{array} | \\ = & | \begin{array}{c} r + (v - 1) λ_{2} & 0 & \dots & 0 \\ λ_{2} & r - λ_{2} & \dots & 0 \\ ⋮ & ⋮ & ⋱ & ⋮ \\ λ_{2} & 0 & \dots & r - λ_{2} \end{array} | \\ = & (r - λ_{2})^{v - 1} (r + (v - 1) λ_{2}) \end{array}$
$r > λ_{2}$ から
$\begin{array}{rcl} r - λ_{2} & \neq & 0 \\ r + (v - 1) λ_{2} = r - λ_{2} + v λ_{2} & \neq & 0 \end{array}$
よって,
$\begin{array}{rcl} d e t (A A^{⊤}) & \neq & 0 \\ ⟺ r a n k (A A^{⊤}) & = & v \end{array}$
行列の階数は積によって広義に減少することから $v = r a n k (A A^{⊤}) \leq r a n k A$ .
一方, $A$ は $v \times b$ 行列であるため, $r a n k A \leq b$ .
以上より $v \leq b$ .

Fisher不等式-系1

S = S (2, k, v) = S (Ω, B)

をSteinerシステムとする.

| B | = b

とすると,

\begin{array}{r} v < b ⟹ k^{2} \leq v \end{array}

$b k = v r$ から
$\begin{array}{rcl} v & < & b \\ v k & < & b k = v r \\ k & < & r \\ k + 1 & \leq & r = \frac{v - 1}{k - 1} \\ k^{2} & \leq & v \end{array}$