ブロックデザイン (数学)

組合せ数学において、ブロックデザイン (block design) とは、実験計画法、ソフトウェアテスト、符号理論、暗号理論、有限幾何、代数幾何学などに広範な応用を持つハイパーグラフの一種である。ブロックデザインであることが文脈から明らかな場合、しばしば単に「デザイン」と呼ばれる。「デザイン」は「計画」と表記されることもある。

定義

有限集合 X と正整数 k, r, λ が与えられているとする。X の元を点と呼び、k 個の元からなる X の部分集合をブロックと呼ぶ。ブロックの集合 B が次の2条件を満たすとき、組 (X, B) を 2-デザインまたは単にデザインという。

• 任意の点 x に対し、x を含む B の元はちょうど r 個である。
• 任意の異なる2点 x, y に対し、x と y を共に含む B の元はちょうど λ 個である。

第2の条件を満たせば自動的に第1の条件を満たすような r が存在するので、第2の条件のみで定義してもよい。

k, r, λ に加え、点の個数 v とブロックの個数 b をデザインのパラメータという。各パラメータの意味を表にまとめると以下の通り。

パラメータ v, b, r, k, λ を持つデザインは、(v, k, λ)-デザインまたは (v, b, r, k, λ)-デザインなどと表記される。パラメータたちは全てが独立ではなく、v, k, λ を与えれば b, r が定まる。実際、パラメータたちの間には、

${\displaystyle bk=vr}$

${\displaystyle \lambda (v-1)=r(k-1)}$

という関係式が成り立つ。ただし、v, k, λ を与えたとしても、(v, k, λ)-デザインが存在するとは限らない。例えば、(43, 7, 1)-デザインは存在しないことが知られている。基本的な事実として、（非自明な）デザインが存在するためには b ≥ v が必要である。これをフィッシャーの不等式という。b = v の場合のデザインは、対称的デザインと呼ばれ、多くの特別な性質を有する。

例

B = { X } とすると、(X, B) は明らかに2-デザインである。これを自明なデザインという。B が X の k 点部分集合全体の集合である場合も、(X, B) は明らかに2-デザインである。これを完全なデザインまたは完備なデザインという。自明でも完全でもない2-デザインを、釣合い型不完備ブロック計画 (balanced incomplete block design) といい、略して BIBD と書く。以下に見るように、BIBD の典型的な例として有限射影平面があり、これは対称的デザインでもある。

射影平面

組合せ論における（有限）射影平面とは、有限個の点の集合 P と直線の集合 L（P の部分集合族）の組 (P, L) であって、以下の3条件を満たすものである。

• 異なる2点を通る直線はちょうどひとつである。
• 異なる2直線はちょうど1点で交わる。
• 四角形（どの3点も同一直線上にない4点）が存在する。

このとき、(P, L) はある正整数 n に対して (n² n 1, n 1, 1)-デザインである。n を射影平面 (P, L) の位数という。n が素数冪 q に等しい場合は、有限体 F_q 上の射影平面が考えられるが、一般には有限体上の射影平面と位数は同じだが同型でない有限射影平面も存在する。位数 n の射影平面のデザインとしてのパラメータについてまとめると、v = b = n² n 1, r = k = n 1, λ = 1 である。v = b は、有限射影平面の点の個数と直線の本数は等しいことを意味する。

最も簡単な q = 2 の場合、F₂ = { 0, 1 } 上の射影平面（ファノ平面）の点は、

P₁ = [0: 0: 1], P₂ = [0: 1: 0], P₃ = [0: 1: 1], P₄ = [1: 0: 0], P₅ = [1: 0: 1], P₆ = [1: 1: 0], P₇ = [1: 1: 1]

の7点であり、直線は

L₁ = { [x: y: z] | x = 0 } = { P₁, P₂, P₃ }

L₂ = { [x: y: z] | y = 0 } = { P₁, P₄, P₅ }

L₃ = { [x: y: z] | z = 0 } = { P₂, P₄, P₆ }

L₄ = { [x: y: z] | x y = 0 } = { P₁, P₆, P₇ }

L₅ = { [x: y: z] | x z = 0 } = { P₂, P₅, P₇ }

L₆ = { [x: y: z] | y z = 0 } = { P₃, P₄, P₇ }

L₇ = { [x: y: z] | x y z = 0 } = { P₃, P₅, P₆ }

の7本である。

X = { P₁, …, P₇ }

B = { L₁, …, L₇ }

とすれば、(X, B) は (7, 3, 1)-デザインである。

一般化

2 以上の整数 t に対し、t-デザインが定義される。上記の定義における第2の条件を次のように変えたものである。

• 任意の異なる t 個の点に対し、その t 個の点を全て含む B の元はちょうど λ 個である。

t もデザインのパラメータのひとつに数えられ、t-(v, k, λ)-デザインなどと表記される。この4つのパラメータを与えれば、残りの b, r は自動的に定まる。どのようなパラメータに対してデザインが存在するか、存在する場合にはそれを分類せよ、というのがデザイン理論における主要な問題である。

t-(v, k, 1)-デザインは、シュタイナーシステムと呼ばれ、S(t, k, v) と書かれる。

関連事項　

• 有限幾何

参考文献

• 日本数学会編『岩波数学辞典』第4版、岩波書店、2007年、317「デザイン理論」の項 ISBN 978-4000803090

外部リンク

• Weisstein, Eric W. "Block Designs". mathworld.wolfram.com (英語).