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

組合せ数学において、ブロックデザイン (block design) とは、実験計画法、ソフトウェアテスト、符号理論、暗号理論、有限幾何、代数幾何学などに広範な応用を持つハイパーグラフの一種である。ブロックデザインであることが文脈から明らかな場合、しばしば単に「デザイン」と呼ばれる。「デザイン」は「計画」と表記されることもある。
定義.
有限集合 "X" と正整数 "k", "r", λ が与えられているとする。"X" の元を点と呼び、"k" 個の元からなる "X" の部分集合をブロックと呼ぶ。ブロックの集合 "B" が次の2条件を満たすとき、組 ("X", "B") を 2-デザインまたは単にデザインという。
第2の条件を満たせば自動的に第1の条件を満たすような "r" が存在するので、第2の条件のみで定義してもよい。
"k", "r", λ に加え、点の個数 "v" とブロックの個数 "b" をデザインのパラメータという。各パラメータの意味を表にまとめると以下の通り。
パラメータ "v", "b", "r", "k", λ を持つデザインは、("v", "k", λ)-デザインまたは ("v", "b", "r", "k", λ)-デザインなどと表記される。パラメータたちは全てが独立ではなく、"v", "k", λ を与えれば "b", "r" が定まる。実際、パラメータたちの間には、
という関係式が成り立つ。ただし、"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条件を満たすものである。
このとき、("P", "L") はある正整数 "n" に対して ("n"2 + "n" + 1, "n" + 1, 1)-デザインである。"n" を射影平面 ("P", "L") の位数という。"n" が素数冪 "q" に等しい場合は、有限体 F"q" 上の射影平面が考えられるが、一般には有限体上の射影平面と位数は同じだが同型でない有限射影平面も存在する。位数 "n" の射影平面のデザインとしてのパラメータについてまとめると、"v" = "b" = "n"2 + "n" + 1, "r" = "k" = "n" + 1, λ = 1 である。"v" = "b" は、有限射影平面の点の個数と直線の本数は等しいことを意味する。
最も簡単な "q" = 2 の場合、F2 = { 0, 1 } 上の射影平面（）の点は、
の7点であり、直線は
の7本である。
とすれば、("X", "B") は (7, 3, 1)-デザインである。
一般化.
2 以上の整数 "t" に対し、"t"-デザインが定義される。上記の定義における第2の条件を次のように変えたものである。
"t" もデザインのパラメータのひとつに数えられ、"t"-("v", "k", λ)-デザインなどと表記される。この4つのパラメータを与えれば、残りの "b", "r" は自動的に定まる。どのようなパラメータに対してデザインが存在するか、存在する場合にはそれを分類せよ、というのがデザイン理論における主要な問題である。
"t"-("v", "k", 1)-デザインは、と呼ばれ、"S"("t", "k", "v") と書かれる。