協会制度

連想スキーム の理論は、統計学の分散分析のための実験計画の理論で生まれました。^{[1] [2] [3]}数学では、連想スキームは代数と組合せ論の両方に属します。代数的組合せ論では、連想スキームは、組合せ設計や誤り訂正符号の理論など、多くのトピックに対する統一的なアプローチを提供します。^{[4] [5]代数学では、連想スキームは}グループを一般化し、連想スキームの理論はグループの線形表現のキャラクター理論を一般化します。^{[6] [7] [8]}

nクラスの関連付けスキームは、集合X と 、X × Xをn  + 1 個のバイナリ関係R ₀、R ₁、 ...、R _nに分割したパーティション Sで構成され、次の条件を満たします。

• ${\displaystyle R_{0}=\{(x,x):x\in X\}}$; これは恒等関係と呼ばれます。
• を定義すると、 R がSに属する場合、R* がSに属することになります。${\displaystyle R^{*}:=\{(x,y):(y,x)\in R\}}$
• の場合、およびとなるの数は、によって決まりますが、およびの特定の選択によっては決まりません。${\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}}$${\displaystyle i}$${\displaystyle j}$${\displaystyle k}$${\displaystyle x}$${\displaystyle y}$

すべての、および に対してである場合、関連スキームは可換です。ほとんどの著者はこの特性を前提としています。ただし、関連スキームの概念はグループの概念を一般化しますが、可換関連スキームの概念は可換グループの概念のみを一般化することに注意してください。 ${\displaystyle p_{ij}^{k}=p_{ji}^{k}}$${\displaystyle i}$${\displaystyle j}$${\displaystyle k}$

対称的な関連スキームとは、それぞれが対称的な関係であるスキームです。つまり、 ${\displaystyle R_{i}}$

• ( x , y ) ∈ R _iならば、 ( y , x ) ∈ R _iです。(または同等に、R * = Rです。)

すべての対称的な関連付けスキームは可換です。

2 つの点xとy は 、 の場合、 i 番目の関連付けと呼ばれます。定義では、xとy がi 番目の関連付けである場合、 とxもi番目の関連付けであるとされています。すべての点のペアは、 の 1 つに対してi番目の関連付けになります。各点はそれ自身の 0 番目の関連付けですが、異なる点が 0 番目の関連付けになることはありません。 xとy がk番目の関連付けである場合、 のi 番目の関連付けであり、 のj 番目の関連付けでもある 点の数は定数です。 ${\displaystyle (x,y)\in R_{i}}$${\displaystyle i}$${\displaystyle z}$${\displaystyle x}$${\displaystyle y}$${\displaystyle p_{ij}^{k}}$

対称的な関連スキームは、ラベル付きの辺を持つ完全グラフとして視覚化できます。グラフには、 の各点に 1 つずつ頂点があり、頂点 と を結ぶ辺は、と が番目の関連である場合にラベルが付けられます。各辺には一意のラベルがあり、ラベルが付けられた固定底辺を持ち、ラベルが付けられた他の辺が および である三角形の数は定数で、底辺の選択によって決まりますが、選択には依存しません。特に、各頂点は というラベルの付いた辺と正確に接続しており、は関係の結合価です。また、に対応する、ラベルが付けられたループが各頂点に存在します。 ${\displaystyle v}$${\displaystyle X}$${\displaystyle x}$${\displaystyle y}$${\displaystyle i}$${\displaystyle x}$${\displaystyle y}$${\displaystyle i}$${\displaystyle k}$${\displaystyle i}$${\displaystyle j}$${\displaystyle p_{ij}^{k}}$${\displaystyle i,j,k}$${\displaystyle p_{ii}^{0}=v_{i}}$${\displaystyle i}$${\displaystyle v_{i}}$ ${\displaystyle R_{i}}$${\displaystyle 0}$${\displaystyle x}$${\displaystyle R_{0}}$

関係は隣接行列によって記述されます。はの隣接行列であり、は の点でラベル付けされた行と列を持つv × v行列です。 ${\displaystyle A_{i}}$${\displaystyle R_{i}}$${\displaystyle i=0,\ldots ,n}$ ${\displaystyle X}$

${\displaystyle \left(A_{i}\right)_{x,y}={\begin{cases}1,&{\mbox{if }}(x,y)\in R_{i},\\0,&{\mbox{otherwise.}}\end{cases}}\qquad (1)}$

対称結合スキームの定義は、v × v (0,1)行列が次の式を満たす と述べることと同等である。${\displaystyle A_{i}}$

I.対称的である、${\displaystyle A_{i}}$

II. （オールワンマトリックス）${\displaystyle \sum _{i=0}^{n}A_{i}=J}$

III. 、${\displaystyle A_{0}=I}$

IV. .${\displaystyle A_{i}A_{j}=\sum _{k=0}^{n}p_{ij}^{k}A_{k}=A_{j}A_{i},i,j=0,\ldots ,n}$

(IV)の左辺の( x , y )番目の要素は、グラフ内のラベルiとjを持つxとyの間の長さ2のパスの数です。の行と列にはが含まれていることに注意してください。 ${\displaystyle A_{i}}$${\displaystyle v_{i}}$ ${\displaystyle 1}$

${\displaystyle A_{i}J=JA_{i}=v_{i}J.\qquad (2)}$

• これらの数字はスキームのパラメータと呼ばれます。また、構造定数とも呼ばれます。${\displaystyle p_{ij}^{k}}$

アソシエーションスキームという用語は、(Bose & Shimamoto 1952)によるものですが、その概念は、(Bose & Nair 1939)にすでに存在していました。^{[9]これらの著者は、統計学者が}部分的にバランスのとれた不完全ブロック設計(PBIBD)と呼ぶものを研究していました。この主題は、(Bose & Mesner 1959)の出版とボーズ-メスナー代数の導入により、代数的な関心の対象となりました。この理論への最も重要な貢献は、符号理論と設計理論とのつながりを認識し、完全に活用した P. Delsarte の論文 (Delsarte 1973) でした。^{[10]一般化は、DG Higman (コヒーレント構成) と}B. Weisfeiler (距離正則グラフ)によって研究されています。

• ${\displaystyle p_{00}^{0}=1}$つまり、 の場合、となり、 となる唯一のものは となります。${\displaystyle (x,y)\in R_{0}}$${\displaystyle x=y}$${\displaystyle z}$${\displaystyle (x,z)\in R_{0}}$${\displaystyle z=x}$
• ${\displaystyle \sum _{i=0}^{k}p_{ii}^{0}=|X|}$; これはパーティションのためです。${\displaystyle R_{i}}$${\displaystyle X}$

グラフの隣接行列は、 行列積と点ごとの積の両方に対して、 （実数または複素数上の）可換かつ結合的な代数を生成します。この結合的で可換な代数は、結合スキームのボーズ・メスナー代数と呼ばれます。 ${\displaystyle A_{i}}$ ${\displaystyle \left(X,R_{i}\right)}$ ${\displaystyle {\mathcal {A}}}$

の行列は対称で互いに可換なので、同時に対角化できます。したがって、は半単純であり、原始冪等性の唯一の基底を持ちます。 ${\displaystyle {\mathcal {A}}}$${\displaystyle {\mathcal {A}}}$ ${\displaystyle J_{0},\ldots ,J_{n}}$

に同型な別の行列代数があり、こちらの方が扱いやすい場合が多いです。 ${\displaystyle (n+1)\times (n+1)}$${\displaystyle {\mathcal {A}}}$

• ジョンソンスキームはJ ( v , k )と表記され、次のように定義されます。S をv個の要素を持つ集合とします。スキームJ ( v , k )の点は、 S のk個の要素を持つ部分集合です。Sの2 つのk要素部分集合A、B は、その共通部分がサイズk  −  iであるとき、 i 番目の関連です。${\displaystyle {v \choose k}}$
• ハミング方式はH ( n , q )と表記され、次のように定義されます。H ( n , q ) の点は、サイズqのセット上のq ⁿ順序のn組です。2つのn組x、y は、正確にi座標 で一致しない場合はi番目の関連付けであると言われます。たとえば、x = (1,0,1,1)、y = (1,1,1,1)、z = (0,0,1,1) の場合、xとy は1 番目の関連付け、xとz は1 番目の関連付け、yとz はH (4,2)の 2 番目の関連付けになります。
• 距離正則グラフGは、 2 つの頂点の 距離がiである場合に、それらの頂点をi番目の関連点として定義することによって、関連スキームを形成します。
• 有限群 Gは、各群元に対してクラスR _{g を}持つ上の関連付けスキームを次のように生成します。各 に対して となります。ここで は群演算です。群の恒等式のクラスはR ₀です。この関連付けスキームは、 Gがアーベル である場合に限り可換です。${\displaystyle X=G}$${\displaystyle g\in G}$${\displaystyle R_{g}=\{(x,y)\mid x=g*y\}}$${\displaystyle *}$
• 具体的な3クラス関連スキーム: ^[11]

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

ハミング方式とジョンソン方式は古典的な符号理論において重要な意味を持っています。

符号理論において、関連スキーム理論は主にコードの距離に関係しています。線形計画法は、与えられた最小距離を持つコードのサイズの上限と、与えられた強度を持つ設計のサイズの下限を生成します。最も具体的な結果は、基礎となる関連スキームが特定の多項式特性を満たす場合に得られます。これは、直交多項式の領域につながります。特に、多項式タイプの関連スキームのコードと設計に対して、いくつかの普遍的な境界が導出されます。

ハミング方式のコードを扱う古典的な符号理論では、マクウィリアムズ変換は、クラウチュク多項式と呼ばれる直交多項式の族を必要とします。これらの多項式は、ハミング方式の距離関係行列の固有値を与えます。

• ブロックデザイン
• ボーズ・メスナー代数
• 組み合わせ設計

• ベイリー、ローズマリー A. (2004)、アソシエーション スキーム: 計画的実験、代数、組合せ論、ケンブリッジ大学出版局、ISBN 978-0-521-82446-0、MR  2047311（草稿の一部はオンラインで閲覧可能です。）
• 坂内 栄一、伊藤 達郎 (1984)、代数的組合せ論 I: アソシエーションスキーム、メンロパーク、カリフォルニア州: ベンジャミン/カミングス、ISBN 0-8053-0490-8、MR  0882540
• Bose, RC ; Mesner, DM (1959)、「部分的にバランスのとれたデザインの連想スキームに対応する線形連想代数について」、Annals of Mathematical Statistics、30 (1): 21–38、doi : 10.1214/aoms/1177706356、JSTOR  2237117、MR  0102157
• Bose, R. C. ; Nair, K. R. (1939)、「部分的にバランスのとれた不完全ブロック設計」、Sankhyā、4 (3): 337–372、JSTOR  40383923
• Bose, R. C. ; Shimamoto, T. (1952)、「2 つの関連クラスを持つ部分的にバランスのとれた不完全ブロック設計の分類と分析」、Journal of the American Statistical Association、47 (258): 151–184、doi :10.1080/01621459.1952.10501161
• Camion, P. (1998)、「18. コードと関連スキーム: コーディングに関連する関連スキームの基本特性」、Pless, VS、Huffman, WC、Brualdi, RA (編)、『コーディング理論ハンドブック』、第 1 巻、Elsevier、pp. 1441–、ISBN 978-0-444-50088-5
• Delsarte, P. (1973)、「符号理論の関連スキームへの代数的アプローチ」、Philips Research Reports (補足 No. 10)、OCLC  641852316
• Delsarte, P.; Levenshtein, VI (1998). 「アソシエーションスキームとコーディング理論」. IEEE Transactions on Information Theory . 44 (6): 2477–2504. doi :10.1109/18.720545.
• デンボウスキー、P. (1968)、有限幾何学、シュプリンガー、ISBN 978-3-540-61786-0
• ゴッズィル、CD（1993）、代数的組合せ論、ニューヨーク：チャップマン＆ホール、ISBN 0-412-04131-6、MR  1220704
• MacWilliams, FJ; Sloane, NJA (1977)、誤り訂正符号の理論、North-Holland Mathematical Library、第 16 巻、Elsevier、ISBN 978-0-444-85010-2
• ストリート、アン・ペンフォールド;ストリート、デボラ・J. (1987)、実験計画の組合せ論、オックスフォード大学出版局 [クラレンドン]、ISBN 0-19-853256-3

• van Lint, JH; Wilson, RM (1992)、A Course in Combinatorics、ケンブリッジ大学出版局、ISBN 0-521-00601-5
• ジーシャン、ポール・ヘルマン (2005a)、「アソシエーション・スキーム：ローズマリー・A・ベイリー著『計画的実験、代数、組合せ論』レビュー」（PDF）、アメリカ数学会報、43（2）：249–253、doi：10.1090/S0273-0979-05-01077-3
• ツィーシャン、ポール・ヘルマン（2005b）、アソシエーションスキームの理論、シュプリンガー、ISBN 3-540-26136-2
• ジーシャン、ポール・ヘルマン（2006）、「アソシエーションスキームの交換条件」、イスラエル数学ジャーナル、151（3）：357–380、doi：10.1007 / BF02777367、MR  2214129、S2CID  120009352