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

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

184
0

  1. Fisher不等式

  2. 自己同型群

  3. アフィン平面

  4. Steinerトリプルシステム

    1. STSの直積


  5. Mathieu群 M11M12

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

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


構成したSteinerシステム

(2,3,7)NEW

定義

Steinerシステム

v点集合Ω={α1,α2,,αv}とその部分集合族B={B1,B2,,Bb}の組(Ω,B)であって, 条件

  • 任意の1ibに対して, |Bi|=k
  • Ωの任意のtαp1,αp2,,αptを取ったとき, αp1,αp2,,αptBiとなるBiBが存在して一意

を満たすものを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)を取れば,
B={(1,2,3),(1,4,7),(1,5,6),(2,4,6),(2,5,7),(3,4,5),(3,6,7)}
と組み上げられる.

構成法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システムの定義も満足していることが確認できる.
B={(1,2,3),(1,4,7),(1,5,6),(2,4,6),(2,5,7),(3,4,5),(3,6,7)}

基本的な性質

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

Ωにおいて, αを含むようなt元の選び方は(v1t1)通り.
Bにおいて, αを含むブロックとしてBiを取る. Bik個の元からαを含むようなt元の選び方は(k1t1)通り.
いま, αを含むブロックの個数をrとしているのだから, αを含むt元の選び方はr(k1t1)通り.
したがって,
r(k1t1)=(k1t1)r=(v1t1)(k1t1)

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

S=S(t,k,v)=S(Ω,B)をSteinerシステムとする. 1itとして, Ωのあるi元部分集合を含むブロックの個数λi(viti)(kiti).

定理1と同様.

k<vを仮定していたのだから,v1k1>1.
辺々(v2)(v3)(vt+1)(k2)(k3)(kt+1)>0を掛けて,
r=v1k1(v2)(v3)(vt+1)(k2)(k3)(kt+1)>(v2)(v3)(vt+1)(k2)(k3)(kt+1)=λ2

 ブロックの個数bt,k,vの関係式を導く.

αΩ,BBとして, αBを満たすような組(α,B)の個数mを求める.
[i] ブロックの選び方はb通り. ブロックの位数はkであるから, 選んだブロックに含まれている元の選び方はk通り.
したがって, m=bk.
[ii] Ωの元の選び方はv通り. ある元を含むブロックの個数をrとしたため, m=vr.
以上より,bk=vr.
r=(v1)(v2)(vt+1)(k1)(k2)(kt+1)から,
b=vrk=v(v1)(v2)(vt+1)k(k1)(k2)(kt+1)=(vt)(kt)

Fisher不等式

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

接続行列

Ω={α1,α2,,αv},B={B1,B2,,Bb}S=S(t,k,v)=S(Ω,B)をSteinerシステムとする. S接続行列とは, 各成分が
aij={1αiBj(1iv,1jb)0otherwise
によって定義された行列A=[aij]である.

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

Sの接続行列をA, Ωのある元を含むブロックの個数をr, ある2元部分集合を含むブロックの個数をλ2として, v次正方行列AA=[bij]を考える.
AAは, Aの行同士の内積を取っていると捉えられるため,
bij={ri=jλ2ij
と書ける.
AAの行列式に関して,
det(AA)=|rλ2λ2λ2rλ2λ2λ2r|=|r+(v1)λ2r+(v1)λ2r+(v1)λ2λ2rλ2λ2λ2r|=|r+(v1)λ200λ2rλ20λ20rλ2|=(rλ2)v1(r+(v1)λ2)
r>λ2から
rλ20r+(v1)λ2=rλ2+vλ20
よって,
det(AA)0rank(AA)=v
行列の階数は積によって広義に減少することからv=rank(AA)rankA.
一方, Av×b行列であるため, rankAb.
以上よりvb.

bk=vrから
v<bvk<bk=vrk<rk+1r=v1k1k2v

とほぼ同様のため省略.

 S(2,q+1,q2+q+1)の形をしたSteinerシステムのことを特に(有限)射影平面と呼び, qを位数という. Fano平面S(2,3,7)は位数が最小の射影平面である.

参考文献

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

この記事を高評価した人

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

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

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

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

投稿者

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

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中
  1. 定義
  2. 基本的な性質
  3. Fisher不等式
  4. 参考文献