ブロックデザイン (数学)
組合せ数学において、ブロックデザイン (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 点の個数、すなわち X の元の個数 b ブロックの個数、すなわち B の元の個数 r ある点を含むブロックの個数 k ひとつのブロックに含まれる点の個数 λ 異なる2つの（より一般の t-デザインの場合は t 個の）点を含むブロックの個数
パラメータ v, b, r, k, λ を持つデザインは、(v, k, λ)-デザインまたは (v, b, r, k, λ)-デザインなどと表記される。パラメータたちは全てが独立ではなく、v, k, λ を与えれば b, r が定まる。実際、パラメータたちの間には、
F2 上の射影平面の模式図。これは (7, 3, 1)-デザインである。 最も簡単な q = 2 の場合、F2 = { 0, 1 } 上の射影平面（ファノ平面）の点は、
- P1 = [0: 0: 1], P2 = [0: 1: 0], P3 = [0: 1: 1], P4 = [1: 0: 0], P5 = [1: 0: 1], P6 = [1: 1: 0], P7 = [1: 1: 1]
の7点であり、直線は
- L1 = { [x: y: z] | x = 0 } = { P1, P2, P3 }
- L2 = { [x: y: z] | y = 0 } = { P1, P4, P5 }
- L3 = { [x: y: z] | z = 0 } = { P2, P4, P6 }
- L4 = { [x: y: z] | x + y = 0 } = { P1, P6, P7 }
- L5 = { [x: y: z] | x + z = 0 } = { P2, P5, P7 }
- L6 = { [x: y: z] | y + z = 0 } = { P3, P4, P7 }
- L7 = { [x: y: z] | x + y + z = 0 } = { P3, P5, P6 }
の7本である。
- X = { P1, …, P7 }
- B = { L1, …, L7 }
とすれば、(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 (英語).
- Block Designのページへのリンク
