ブロックデザイン

組み合わせ数学において、ブロックデザインとは、集合と、ブロックと呼ばれる部分集合の族から構成される接続構造であり、各要素の出現回数が特定の条件を満たすように選択され、ブロックの集合が対称性（バランス）を示すように構成されます。ブロックデザインは、実験計画法、有限幾何学、物理化学、ソフトウェアテスト、暗号理論、代数幾何学など、多くの分野で応用されています。

特に指定がない場合、ブロック設計という用語は通常、バランスのとれた不完全ブロック設計( BIBD )、具体的には (また同義語として) 2-設計を指し、これは実験計画法への応用により、歴史的に最も集中的に研究されてきたタイプです。^{[ 1 ] [ 2 ]}その一般化はt-設計として知られています。

元の集合のすべてのt部分集合が等しい数 (つまりλ ) のブロックに現れる場合、そのデザインは( tまで)バランスが取れていると言われます。t が指定されていない場合、通常は 2 とみなすことができ、これは各要素のペアが同じ数のブロックに現れ、デザインがペアワイズバランスであることを意味します。t = 1の場合、各要素は同じ数のブロック (複製数、rで表される) に現れ、デザインは正則であると言われます。すべてのブロックが同じサイズ (通常はkで表される) を持つブロックデザインは、均一または適切と呼ばれます。この記事で説明するデザインはすべて均一です。必ずしも均一ではないブロックデザインも研究されており、t = 2 の場合、文献ではペアワイズバランスデザイン(PBD) という一般的な名前で知られています。tまでバランスが取れている均一なデザインは、 tのより小さい値でもバランスが取れています(ただし、λ の値は異なります)。たとえば、ペアワイズでバランスが取れている ( t = 2) デザインは、正則 ( t = 1) でもあります。バランスの要件が満たされない場合でも、 t個の部分集合をn 個のクラスに分割でき、各クラスが独自の (異なる) λ値を持つ場合、デザインは部分的にバランスが取れている可能性があります。t = 2の場合、これらはPBIBD( n ) デザインとして知られており、そのクラスは関連付けスキームを形成します。           

デザインは通常、不完全であると言われ（または想定され）、これはブロックの集合がすべての可能なk部分集合ではないことを意味し、したがって自明なデザインは除外されます。

ブロックデザインには繰り返しブロックがある場合とない場合があります。繰り返しブロックのないデザインはシンプルと呼ばれ、^{[ 3 ]}この場合、ブロックの「ファミリー」はマルチセットではなくセットになります。

統計学において、ブロックデザインの概念は、ブロック内に要素が複数含まれる非二値ブロックデザインに拡張されることがある（統計学の「ブロッキング」を参照）。そこでは、各要素が合計で同じ回数出現するデザインを等複製と呼び、デザインが二値である場合にのみ、規則的なデザインとなる。非二値デザインの出現回数行列には、各ブロック内で各要素が繰り返される回数が示される。

最も単純なタイプの「バランス型」設計（t = 1）は、戦術構成または1設計として知られています。幾何学における対応する接続​​構造は、単に構成として知られています（構成（幾何学）を参照） 。このような設計は均一かつ規則的です。各ブロックにはk個の要素が含まれ、各要素はr個のブロックに含まれています。セット要素の数vとブロックの数bは、次の関係にあります。${\displaystyle bk=vr}$これは、要素の出現回数の合計です。

行と列の合計が一定であるすべての二値行列は、正則な均一ブロック設計の隣接行列です。また、各構成には、その隣接グラフまたはレヴィグラフとして知られる、対応する正則な二部グラフが存在します。

有限集合X (要素は点と呼ばれる) と整数k、r、λ ≥ 1が与えられたとき、 2-デザイン(またはBIBD、バランスのとれた不完全ブロックデザイン) B を、ブロックと呼ばれるXのk要素部分集合の族として定義します。このとき、 X内の任意のxはr個のブロックに含まれ、 X内の任意の異なる点xとyのペアはλ 個のブロックに含まれます。ここで、 X内の任意のx がr個のブロックに含まれるという条件は、以下に示すように冗長です。

ここで、v （ Xの要素数、点と呼ばれる）、b（ブロック数）、k、r、λは設計のパラメータです。（退化した例を避けるため、 v > kであると仮定し、どのブロックも集合のすべての要素を含まないようにします。これが、これらの設計の名前にある「不完全」の意味です。）表で表すと次のようになります。

この設計は ( v , k , λ )-設計または ( v , b , r , k , λ )-設計と呼ばれます。パラメータはすべて独立しているわけではなく、v、k、λ はbとrを決定し、 v、k、λのすべての組み合わせが可能なわけではありません。これらのパラメータを関連付ける 2 つの基本方程式は次のとおりです。

${\displaystyle bk=vr,}$

Bがブロックであり、pがそのブロック内の点であるようなペア ( B , p )の数を数えることによって得られ、

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

固定されたxに対して、xとy が異なる点であり、B がそれら両方を含むブロックであるような3 つ組 ( x、y、B )を数えることによって得られる。この式は、すべてのxに対して、明示的に仮定しなくてもrが定数 ( xに依存しない)であることを証明しており、したがって、 X内の任意のx がr個のブロックに含まれるという条件は冗長であり、r は他のパラメータから計算できることを証明している。

結果として得られるbとrは整数でなければならず、これはv、k、λに条件を課す。これらの条件は十分ではなく、例えば(43,7,1)デザインは存在しない。^{[ 4 ]}

2-デザインの次数は n = r − λ と定義されます。2-デザインの補集合は、点集合X 内の各ブロックをその補集合に置き換えることによって得られます。これもまた 2-デザインであり、パラメータはv ′ = v、b ′ = b、r ′ = b − r、k ′ = v − k、λ ′ = λ + b − 2 rです。2-デザインとその補集合は同じ次数を持ちます。          

統計学者ロナルド・フィッシャーにちなんで名付けられたフィッシャーの不等式という基本定理は、任意の2-デザインにおいてb ≥ vである。  

これらのデザインに関する、やや意外で自明ではない（しかし非常に一般的な）組み合わせ論的結果は、点が等間隔または不等間隔の任意の選択された数値の集合で表される場合、すべてのブロック和（つまり、与えられたブロック内のすべての点の合計）を一定にできるような集合の選択は存在しないということです。^{[ 5 ] [ 6 ]ただし、部分的にバランスのとれた不完全なブロックデザインなどの他のデザインでは、これが可能かもしれません。そのような多くのケースについては、 [ 7 ]}で議論されています。しかし、部分的にバランスのとれた不完全なブロックデザインと見なせる魔法の正方形や魔法の長方形については、自明に観察することもできます。

フィッシャーの不等式が等しい場合、つまり点とブロックの数が等しい2デザインは、対称デザインと呼ばれます。^{[ 9 ]}対称デザインは、点の数が同じすべての2デザインの中でブロックの数が最小です。

対称デザインでは、r = kとb = vが成り立ち、任意の 2-デザインでは一般には成り立たないものの、対称デザインでは任意の 2 つの異なるブロックがλ点で交わります。^{[ 10 ]} Ryserの定理は逆を示しています。Xがv要素の集合であり、Bがk要素の部分集合 (「ブロック」)のv要素の集合で、任意の 2 つの異なるブロックがちょうど λ 点を共有する場合、( X, B ) は対称ブロックデザインです。^{[ 11 ]}

対称設計のパラメータは以下を満たす

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

これはvに強い制約を課すため、点の数は決して任意ではない。ブルック・ライザー・チョウラ定理は、これらのパラメータに関して対称的な設計が存在するための必要条件を与えるが、十分条件ではない。

以下は、対称的な2-デザインの重要な例です。

解決可能な2-デザインとは、ブロックを集合（並列クラスと呼ばれる）に分割でき、各集合がBIBDの点集合の分割を形成するBIBDのことである。並列クラスの集合は、デザインの解決と呼ばれる。

2-( v , k , λ)分解可能な設計がc個の並列クラスを持つ場合、b  ≥ v + c − 1となる。 ^{[ 20 ]}     

したがって、対称設計では非自明な（並列クラスが複数ある）解決は不可能である。^{[ 21 ]}

典型的な解ける 2-デザインは有限アフィン平面である。有名な15 人の女子生徒問題の解は 2-(15,3,1) デザインの解である。^{[ 22 ]}

任意の正の整数tに対して、tデザインB は、ブロックと呼ばれるXのk要素部分集合のクラスであり、 Xのすべての点xがちょうどr個のブロックに現れ、すべてのt要素部分集合Tがちょうど λ 個のブロックに現れる。数値v ( Xの要素数)、b (ブロック数)、k、r、λ、およびtは、デザインのパラメータである。このデザインはt - ( v、k、λ)-デザインと呼ばれることがある。ここでも、これらの 4 つの数値はbとrを決定し、4 つの数値自体は任意に選択することはできない。方程式は次のようになる。

${\displaystyle \lambda _{i}=\lambda \left.{\binom {v-i}{t-i}}\right/{\binom {k-i}{t-i}}{\text{ for }}i=0,1,\ldots ,t,}$

ここで、λ _iは任意のi要素の点集合を含むブロックの数であり、 λ _t = λ である。

ご了承ください${\displaystyle b=\lambda _{0}=\lambda {v \choose t}/{k \choose t}}$そして${\displaystyle r=\lambda _{1}=\lambda {v-1 \choose t-1}/{k-1 \choose t-1}}$。

定理：^{[ 23 ]}任意のt -( v , k ,λ)-デザインは、 1 ≤ s ≤ tを満たす任意のsに対して、 s -( v , k ,λ _s )-デザインでもある。（「ラムダ値」は上記のように変化し、sに依存することに注意。）    

この定理の帰結として、t ≥ 2 のすべてのtデザインは 2 デザインでもある。

t - ( v , k ,1)-デザインはシュタイナーシステムと呼ばれます。

ブロックデザインという用語は、通常、2つのデザインを意味します。

nクラス関連スキームは、サイズvの集合Xと、X × Xをn + 1 個の二項関係R ₀、R ₁、 ...、R _nに分割したSから構成される。関係 R _iの要素のペアはi番目の関連要素と呼ばれる。X の各要素はn _i i番目の関連要素を持つ。さらに、次のようになる。 

• ${\displaystyle R_{0}=\{(x,x):x\in X\}}$そしてそれは同一性関係と呼ばれます。
• 定義する${\displaystyle R^{*}:=\{(x,y)\mid (y,x)\in R\}}$RがSに含まれる場合、R*はSに含まれる。
• もし${\displaystyle (x,y)\in R_{k}}$、その数${\displaystyle z\in X}$そのため${\displaystyle (x,z)\in R_{i}}$そして${\displaystyle (z,y)\in R_{j}}$定数です${\displaystyle p_{ij}^{k}}$i、j、kに依存するが、 xとyの特定の選択には依存しない。

結合スキームは、以下の条件を満たす場合に可換である。${\displaystyle p_{ij}^{k}=p_{ji}^{k}}$すべてのi、j、kについて。ほとんどの著者はこの性質を仮定している。

n 個の関連クラスを持つ部分的にバランスのとれた不完全なブロック設計( PBIBD( n )) は、サイズkのb個のブロックを持ち、各要素がr個のブロックに現れるv集合 Xに基づくブロック設計であり、 X上に定義されたn個のクラスを持つ関連スキームが存在し、要素xとyがi番目の関連要素 (1 ≤ i ≤ n)である場合、それらは正確にλ _i個のブロックに一緒に存在する。

PBIBD( n )は関連付けスキームを決定するが、その逆は成り立たない。^{[ 29 ]}

例

A (3)を、集合X = {1,2,3,4,5,6} 上の 3 つの関連クラスを持つ次の関連スキームとする。( i , j ) エントリは、要素iとj が関係 R _{sにある場合に}sとなる。

A (3)に基づくPBIBD(3)のブロックは以下のとおりです。

この PBIBD(3) のパラメータは、v  =  6、b  =  8、k  =  3、r  =  4、λ ₁  =  λ ₂  =  2、λ ₃  =  1 です。また、関連付けスキームでは、n ₀  = n ₂ = 1、n ₁ = n ₃ = 2となります。 ^{[ 30 ]}関係行列 M は       

${\displaystyle {\begin{pmatrix}1&1&1&1&0&0&0&0\\1&1&0&0&1&1&0&0\\0&0&1&1&1&1&0&0\\1&0&1&0&0&0&1&1\\0&1&0&0&1&0&1&1\\0&0&0&1&0&1&1&1\end{pmatrix}}}$

そして同時発生行列MM ^Tは

${\displaystyle {\begin{pmatrix}4&2&2&2&1&1\\2&4&2&1&2&1\\2&2&4&1&1&2\\2&1&1&4&2&2\\1&2&1&2&4&2\\1&1&2&2&2&4\\\end{pmatrix}}}$

そこからλとrの値を求めることができる。

ブロック計画法という数学的概念は、実験計画法という統計的枠組みの中で生まれた。これらの計画法は、分散分析（ANOVA）の手法を応用する際に特に有用であった。現在でも、ブロック計画法は重要な分野として活用されている。

この分野の起源は生物学的応用に基づいているが（既存の用語の一部も同様である）、その設計はソフトウェアテストなど、体系的な比較が行われる多くの応用分野で使用されている。

ブロック設計のインシデンス行列は、誤り訂正符号として使用される興味深いブロック符号の自然な源泉を提供する。インシデンス行列の行は、パルス位置変調の形式でシンボルとしても使用される。^{[ 36 ]}

• 入射ジオメトリ
• シュタイナーシステム
• 一部実施要因計画

• Aschbacher, Michael (1971). 「対称ブロックデザインの共線群について」 . Journal of Combinatorial Theory . Series A. 11 (3): 272– 281. doi : 10.1016/0097-3165(71)90054-9 .
• アスムス、EF; キー、JD (1992) 『デザインとそのコード』ケンブリッジ：ケンブリッジ大学出版局、ISBN 0-521-41361-3
• ベス、トーマス；ユングニッケル、ディーター；レンツ、ハンフリート（1986）、『デザイン理論』、ケンブリッジ大学出版局第2版​​（1999年）ISBN 978-0-521-44432-3。
• Bose, RC (1949)、「バランスのとれた不完全ブロック計画におけるフィッシャーの不等式に関する注記」、Annals of Mathematical Statistics、20 (4): 619–620、doi : 10.1214/aoms/1177729958
• Bose, R.  C. ; Shimamoto, T. (1952)、「2つの関連クラスを持つ部分的にバランスのとれた不完全ブロック設計の分類と分析」、Journal of the American Statistical Association、47 (258): 151–184、doi : 10.1080/01621459.1952.10501161
• キャメロン、PJ; ヴァン・リント、JH (1991)、デザイン、グラフ、コードとそのリンク、ケンブリッジ大学出版局、ISBN 0-521-42385-6
• コルボーン、チャールズ・J.、ディニッツ、ジェフリー・H. (2007)、『組合せ設計ハンドブック（第2 版）』、ボカラトン：チャップマン＆ホール/CRC、ISBN 978-1-58488-506-1
• Fisher, RA (1940)、「不完全なブロックにおける問題のさまざまな可能な解の検討」、優生学年報、10 : 52–75、doi : 10.1111/j.1469-1809.1940.tb02237.x、hdl : 2440/15239
• Hall, Marshall Jr. (1986)、組合せ論（第2 版）、ニューヨーク：Wiley-Interscience、ISBN 0-471-09138-3
• ヒューズ、DR; パイパー、EC (1985)、デザイン理論、ケンブリッジ：ケンブリッジ大学出版局、ISBN 0-521-25754-9
• Kaski, Petteri; Östergård, Patric (2008). " k = 11の複葉機はちょうど 5 つ存在する". Journal of Combinatorial Designs . 16 (2): 117– 127. doi : 10.1002/jcd.20145 . MR 2384014 . S2CID 120721016 .  
• ランダー、ES（1983）『対称デザイン：代数的アプローチ』ケンブリッジ大学出版局、ISBN 978-0-521-28693-0
• Lindner, CC; Rodger, CA (1997)、デザイン理論、ボカラトン：CRC Press、ISBN 0-8493-3986-3
• Raghavarao, Damaraju (1988).実験計画における構成と組み合わせ問題. Dover. ISBN 978-0-486-65685-4。
• Raghavarao, Damaraju ; Padgett, LV (2005年10月11日).ブロックデザイン：解析、組み合わせ論、および応用. World Scientific. ISBN 978-981-4480-23-9。
• Ryser, Herbert John (1963)、「8. 組合せデザイン」、組合せ数学、Carus Mathematical Monographs、第14巻 、アメリカ数学協会、96–130ページ、ISBN  978-1-61444-014-7{{citation}}ISBN /日付の不一致（ヘルプ）
• Salwach, Chester J.; Mezzaroba, Joseph A. (1978). " k = 9の 4 つの複平面" . Journal of Combinatorial Theory . Series A. 24 (2): 141– 145. doi : 10.1016/0097-3165(78)90002-X .
• Khattree, Ravindra (2019). 「定数ブロック和バランス不完全ブロック設計の非存在に関する注記」. Communications in Statistics - Theory and Methods . 48 (20): 5165–5168 . doi : 10.1080/03610926.2018.1508715 . S2CID 125795689 . 
• Khattree, Ravindra (2022). 「等複製定数ブロック和設計の構築について」. Communications in Statistics - Theory and Methods . 51 (2): 4434–4450 . doi : 10.1080/03610926.2020.1814816 . S2CID 225335042 . 
• Shrikhande, SS ; Bhat-Nayak, Vasanti N. (1970), "Non-isomorphic solutions of some balanced incomplete block designs I", Journal of Combinatorial Theory , 9 (2): 174– 191, doi : 10.1016/S0021-9800(70)80024-2
• スティンソン、ダグラス R. (2003)、『組合せ設計：構成と分析』、シュプリンガー、ISBN 0-387-95487-2
• ストリート、アン・ペンフォールド、ストリート、デボラ・J. (1987).実験計画法の組み合わせ論. オックスフォード大学出版局 [クラレンドン]. ISBN 0-19-853256-3。
• van Lint, JH; Wilson, RM (1992).組合せ論入門. Cambridge University Press. ISBN 978-0-521-41057-1。

• DesignTheory.Org：組み合わせ論的、統計的、実験的なブロック設計のデータベース。ソフトウェアおよびその他のリソースは、ロンドン大学クイーン・メアリー・カレッジ数理科学部が提供しています。
• デザイン理論リソース：ピーター・キャメロン氏によるウェブベースのデザイン理論リソースのページ。
• ワイスタイン、エリック・W. 「ブロックデザイン」。マスワールド。