結合構造基礎の基礎
結合構造とは
結合関係を表す理論としては無向グラフと無向グラフなどのグラフ理論やそれらのグラフを一般化したハイパーグラフが有名である。
このハイパーグラフをより現代幾何学や組合せ論で扱いやすくなるように定義しなおしたのが次で紹介する結合構造である。
結合構造（接続構造）
空でない集合$\mathcal{P}$、$\mathcal{P}$と共通を持たない集合$\mathcal{L}$、$\mathcal{P}$と$\mathcal{L}$上の関係$\mathcal{I} \subseteq \mathcal{P} \times \mathcal{L}$からなる組$S = \paren{\mathcal{P},\ \mathcal{L},\ \mathcal{I}}$を（二次元）結合構造(incidence structure)という。
また、$\mathcal{P}$の元を点（point）、$\mathcal{L}$の元を直線（line）、$\mathcal{I}$の元を旗（flag）という。さらに、$\mathcal{I}$は旗集合の他に結合関係（incidence relation）と呼ぶこともしばしばある。
なお、簡単のために$\mathcal{P}\!\paren{S},\ \mathcal{L}\!\paren{S},\ \mathcal{I}\!\paren{S}$をそれぞれ結合構造$S$の点集合$\mathcal{P}$、直線集合$\mathcal{L}$、旗集合$\mathcal{I}$のことと略記する。
組合せ論では、有限の対象を扱うのが一般的なため結合構造でも有限版が定義される。
結合構造$S$に対して$\mathcal{P}\!\paren{S},\ \mathcal{L}\!\paren{S},\ \mathcal{I}\!\paren{S}$がそれぞれ有限のとき$S$を有限結合構造、または単に結合構造という。
部分集合との同一視
$S$を結合構造とする。
$A \in \mathcal{P}\!\paren{S}$に対して$\Gamma_{\mathcal{L}}\!\paren{A} := \brace{l \in \mathcal{L}\!\paren{S} \mid \paren{A,\ l} \in \mathcal{I}\!\paren{S}}$、
$l \in \mathcal{L}\!\paren{S}$に対して$\Gamma_{\mathcal{P}}\!\paren{l} := \brace{A \in \mathcal{P}\!\paren{S} \mid \paren{A,\ l} \in \mathcal{I}\!\paren{S}}$とする。
このとき$\Gamma_{\mathcal{L}}\!\paren{A}$を点$A$を通る直線の集合、$\Gamma_{\mathcal{P}}\!\paren{l}$を直線$l$上にある点の集合という。そして、直線$l$を$\Gamma_{\mathcal{P}}\!\paren{l}$と同一視して点$A$が直線$l$上にあるときに$A \in l$と表記する。
このとき直線$l,\ m \in \mathcal{L}\!\paren{S}$に対して、$\Gamma_{\mathcal{P}}\!\paren{l} \cap \Gamma_{\mathcal{P}}\!\paren{m}$の元を$l$と$m$の交点という。一般にこの交点の集合を$l \cap m$と表記する。この交点の集合が一点の集合となるときその一点と同一視して$l \cap m$のことを$l$と$m$の交点と呼ぶこともしばしばある。
$l \neq m \in \mathcal{L}\!\paren{S}$であっても$\Gamma_{\mathcal{P}}\!\paren{l} = \Gamma_{\mathcal{P}}\!\paren{m} $が成り立つこともある。これは直線が重なることを意味する。このことは組合せ論で重複を許す組み合わせのこととなるため、一般に扱うのが難しい。そこでこの直線の重なりがない場合を特別視して結合構造$S$を単純な結合構造ということもある。
結合構造の例
定義ばかりではつまらないので、結合構造の例をいくつか挙げてみる。
点を駅、直線を路線、旗を路線と駅の関係とすると路線図は結合構造とみることができる。
構造から構造の生成
構造を調べるのに単体では扱うのが難しいので、ある意味で対となる構造を生みだして考えることが多い。例えば、「数えるために全体からそれ以外を引く」、「群$G$の構造を調べるために反対群$G^{\text{op}}$を考える」、「圏論の双対概念」など幾らでもある。
結合構造でも似たようなことをする。そこで、補構造と双対構造を紹介する。
結合構造$S$に対し、$\mathcal{I}^{\prime}\!\paren{S} := \brace{\paren{A,\ l} \in \mathcal{P}\!\paren{S} \times \mathcal{L}\!\paren{S} \mid \paren{A,\ l} \notin \mathcal{I}\!\paren{S}}$とする。
このとき組$\paren{\mathcal{P}\!\paren{S},\ \mathcal{L}\!\paren{S},\ \mathcal{I}^{\prime}\!\paren{S}}$を$S$の補構造と呼ぶ。
これを$S^{c}$と表記する。
同じく組合せ論の一つであるグラフ理論においてのグラフの補構造（補グラフ）は、ここで定義した方法では定義できない。ここで定義できるのは（無向）ハイパーグラフの補構造である。グラフの補構造ではない理由は、辺で接続していない頂点の集合が必ずしもサイズが２になるわけではないためである。
もちろん補構造の補構造は元に戻る。
$\paren{S^{c}}^{c} = S$が成り立つ。
$$ \begin{eqnarray} \mathcal{I}\!\paren{\paren{S^{c}}^{c}} && = && \mathcal{I}^{\prime}\!\paren{S^{c}}\\ && = && \brace{\paren{A,\ l} \in \mathcal{P}\!\paren{S^{c}} \times \mathcal{L}\!\paren{S^{c}} \mid \paren{A,\ l} \notin \mathcal{I}\!\paren{S}} \\ && = && \brace{\paren{A,\ l} \in \mathcal{P}\!\paren{S} \times \mathcal{L}\!\paren{S} \mid \paren{A,\ l} \in \mathcal{I}\!\paren{S^{c}}^{c}} \\ && = && \brace{\paren{A,\ l} \in \mathcal{P}\!\paren{S} \times \mathcal{L}\!\paren{S} \mid \paren{A,\ l} \in \mathcal{I}^{\prime}\!\paren{S}^{c}} \\ && = && \brace{\paren{A,\ l} \in \mathcal{P}\!\paren{S} \times \mathcal{L}\!\paren{S} \mid \paren{A,\ l} \in \brace{\paren{A,\ l} \in \mathcal{P}\!\paren{S} \times \mathcal{L}\!\paren{S} \mid \paren{A,\ l} \notin \mathcal{I}\!\paren{S}}^{c}} \\ && = && \brace{\paren{A,\ l} \in \mathcal{P}\!\paren{S} \times \mathcal{L}\!\paren{S} \mid \paren{A,\ l} \in \paren{\mathcal{I}\!\paren{S}^{c}}^{c}} \\ && = && \brace{\paren{A,\ l} \in \mathcal{P}\!\paren{S} \times \mathcal{L}\!\paren{S} \mid \paren{A,\ l} \in \mathcal{I}\!\paren{S}} \\ && = && \mathcal{I}\!\paren{S} \\ \end{eqnarray} $$
実はこの補構造は、次の結合行列を用いて定義できる。
$S$を結合構造とする。このとき行列$B := \paren{\fnp{B}{A,\ l}}_{A \in \mathcal{P}\!\paren{S},\ l \in \mathcal{L}\!\paren{S}}$（点や直線は適当な順番に並んでおり、行列$B$のインデックスを定めているものとする）を
$$
\fnp{B}{A,\ l} =
\begin{cases}
1 & (A \times l \in \mathcal{I}\!\paren{S}) \\
0 & (\text{otherwise})
\end{cases}
$$
で定義する。この行列$B$を$S$の結合行列、または接続行列(incidence matrix,
Wikipedia
)という。
そして、$\fnp{B}{S}$を結合構造$S$の結合行列$B$のことと略記する。
この結合行列を用いると補構造は次で定義される。
$S$を結合構造とし、行列$J$を成分がすべて$1$の行列とする。
このとき行列$J - \fnp{B}{S}$を接続行列として持つ結合構造を$S$の補構造という。
証明は自明なので省略する。
次は、双対構造を説明する。
結合構造$S$に対し、組$\paren{\mathcal{L}\!\paren{S},\ \mathcal{P}\!\paren{S},\ \brace{\paren{l,\ p} \mid \paren{p,\ l} \in \mathcal{I}\!\paren{S}}}$を$S$の双対構造という。
これを$S^{\ast}$と表記する。
双対構造も同様に次が成り立つ。
${\paren{S^{\ast}}}^{\ast} = S$が成り立つ。
そして、双対構造も結合行列で定義できる。
$S$を結合構造とする。
このとき結合行列$\fnp{B}{S}$の転置行列${}^{t}\fnp{B}{S}$を接続行列として持つ結合構造を$S$の双対構造という。
こちらの定義の同値性も自明である。
元の構造のクラス次第では補構造や双対構造は同じクラスになるので調べるのに便利な時がしばしば存在する。
よく使われる調べ方
補構造や双対構造以外にもよく使われる調べ方が他にもある。
ある種の正則条件の設定
先ほど出てきた扱いやすいクラスを得るための条件である、ある種の正則条件の設定である。
「任意の異なる二点を通る直線はただ一つ」と「任意の直線は二つ以上の点からなる」、「直線が二本以上存在する」という条件を結合構造が満たすとき、その結合構造を線形幾何という。
ここでは直線をブロックと呼ぶことにする。
$v \gt k \gt t$となる正整数 $t,\ v,\ k,\ \lambda$に対して「点の数は$v$個である。」、「各ブロックに含まれる点の数は$k$個である。」、「任意の相異なる$t$個の点に対してそれらを含むブロックの個数は$\lambda$個であり、そのブロックの個数は$t$個の点の取り方によらない。」を結合構造が満たすとき、その結合構造は$t$-$\paren{v,\ k,\ \lambda}$デザインという。
なお、$2$-$\paren{v,\ 2,\ \lambda}$は無向グラフとしても見ることができる。
準同型写像
$S$と$S^{\prime}$を結合構造とする。$f=\paren{f_\mathcal{P},\ f_\mathcal{L}}$が次の三つの条件を満たしているとき、$f$を$S$から$S^{\prime}$への準同型写像という。
- $f_\mathcal{P}$は$\mathcal{P}\!\paren{S}$から$\mathcal{P}\!\paren{S^{\prime}} $への写像である。
- $f_\mathcal{L}$は$\mathcal{L}\!\paren{S}$から$\mathcal{L}(S^{\prime})$への写像である。
- $\paren{A,\ l} \in \mathcal{I}\!\paren{S} \implies \paren{f_\mathcal{P}\!\paren{A},\ f_\mathcal{L}\!\paren{l}} \in \mathcal{I}\!\paren{S^{\prime}}$
一般的な準同型の定義と同様に逆写像、同型も定義される。また、有限で単純な結合構造から自身への自己同型写像のとき自己同型群を置換群とみることで、置換群の旗集合に対して結合構造への置換群による作用が定義できる。同様にして結合構造への群の作用も定義できる。（これらの定義を紹介すると長くなりすぎるのでここでは説明しない。）
おわりに
今回は結合構造の利用については解説していないが、今後どこかで書くと思う。
以上です。