Block design

ウィキペディア

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

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/03/03 00:57 UTC 版)

組合せ数学において、ブロックデザイン (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 が定まる。実際、パラメータたちの間には、

$bk=vr$

F₂ 上の射影平面の模式図。これは (7, 3, 1)-デザインである。

最も簡単な 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 (英語).