3
現代数学解説
文献あり

結合構造基礎の基礎

259
1

結合構造とは

結合関係を表す理論としては無向グラフと無向グラフなどのグラフ理論やそれらのグラフを一般化したハイパーグラフが有名である。
このハイパーグラフをより現代幾何学や組合せ論で扱いやすくなるように定義しなおしたのが次で紹介する結合構造である。

結合構造(接続構造)

結合構造(接続構造)

空でない集合PPと共通を持たない集合LPL上の関係IP×Lからなる組S=(P, L, I)を(二次元)結合構造(incidence structure)という。
また、Pの元を点(point)、Lの元を直線(line)、Iの元を旗(flag)という。さらに、Iは旗集合の他に結合関係(incidence relation)と呼ぶこともしばしばある。

なお、簡単のためにP(S), L(S), I(S)をそれぞれ結合構造Sの点集合P、直線集合L、旗集合Iのことと略記する。

組合せ論では、有限の対象を扱うのが一般的なため結合構造でも有限版が定義される。

有限結合構造

結合構造Sに対してP(S), L(S), I(S)がそれぞれ有限のときSを有限結合構造、または単に結合構造という。

部分集合との同一視

直線状の点と交点

Sを結合構造とする。
AP(S)に対してΓL(A):={lL(S)(A, l)I(S)}
lL(S)に対してΓP(l):={AP(S)(A, l)I(S)}とする。
このときΓL(A)を点Aを通る直線の集合、ΓP(l)を直線l上にある点の集合という。そして、直線lΓP(l)と同一視して点Aが直線l上にあるときにAlと表記する。

このとき直線l, mL(S)に対して、ΓP(l)ΓP(m)の元をlmの交点という。一般にこの交点の集合をlmと表記する。この交点の集合が一点の集合となるときその一点と同一視してlmのことをlmの交点と呼ぶこともしばしばある。

lmL(S)であってもΓP(l)=ΓP(m)が成り立つこともある。これは直線が重なることを意味する。このことは組合せ論で重複を許す組み合わせのこととなるため、一般に扱うのが難しい。そこでこの直線の重なりがない場合を特別視して結合構造Sを単純な結合構造ということもある。

結合構造の例

定義ばかりではつまらないので、結合構造の例をいくつか挙げてみる。

無向グラフとハイパーグラフ

点を頂点、直線を辺、旗を頂点と辺の結合関係とすると無向グラフやハイパーグラフは結合構造とみることができる。(画像はそれぞれグラフ理論( Wikipedia )、ハイパーグラフ( Wikipedia )から拝借してます。)

無向グラフ 無向グラフ
ハイパーグラフ ハイパーグラフ

路線図

点を駅、直線を路線、旗を路線と駅の関係とすると路線図は結合構造とみることができる。

ユークリッド平面などの平面空間

点を平面上の点、直線を平面上の点、旗を直線と点の包含関係とすると平面は結合構造とみることができる。なお、この結合構造は有限とは限らない。
例えば、ユークリッド空間( Wikipedia )は無限結合構造、有限幾何学( Wikipedia )で良く使われる位数3のアフィン平面や位数3のファノ平面は有限結合構造である。

構造から構造の生成

構造を調べるのに単体では扱うのが難しいので、ある意味で対となる構造を生みだして考えることが多い。例えば、「数えるために全体からそれ以外を引く」、「群Gの構造を調べるために反対群Gopを考える」、「圏論の双対概念」など幾らでもある。
結合構造でも似たようなことをする。そこで、補構造と双対構造を紹介する。

補構造

結合構造Sに対し、I(S):={(A, l)P(S)×L(S)(A, l)I(S)}とする。
このとき組(P(S), L(S), I(S))Sの補構造と呼ぶ。
これをScと表記する。

補グラフグラフの補構造

同じく組合せ論の一つであるグラフ理論においてのグラフの補構造(補グラフ)は、ここで定義した方法では定義できない。ここで定義できるのは(無向)ハイパーグラフの補構造である。グラフの補構造ではない理由は、辺で接続していない頂点の集合が必ずしもサイズが2になるわけではないためである。

もちろん補構造の補構造は元に戻る。

(Sc)c=Sが成り立つ。

I((Sc)c)=I(Sc)={(A, l)P(Sc)×L(Sc)(A, l)I(S)}={(A, l)P(S)×L(S)(A, l)I(Sc)c}={(A, l)P(S)×L(S)(A, l)I(S)c}={(A, l)P(S)×L(S)(A, l){(A, l)P(S)×L(S)(A, l)I(S)}c}={(A, l)P(S)×L(S)(A, l)(I(S)c)c}={(A, l)P(S)×L(S)(A, l)I(S)}=I(S)

実はこの補構造は、次の結合行列を用いて定義できる。

結合行列

Sを結合構造とする。このとき行列B:=(B(A, l))AP(S), lL(S)(点や直線は適当な順番に並んでおり、行列Bのインデックスを定めているものとする)を
B(A, l)={1(A×lI(S))0(otherwise)
で定義する。この行列BSの結合行列、または接続行列(incidence matrix, Wikipedia )という。
そして、B(S)を結合構造Sの結合行列Bのことと略記する。

この結合行列を用いると補構造は次で定義される。

補構造(結合行列を用いた定義)

Sを結合構造とし、行列Jを成分がすべて1の行列とする。
このとき行列JB(S)を接続行列として持つ結合構造をSの補構造という。

証明は自明なので省略する。

次は、双対構造を説明する。

双対構造

結合構造Sに対し、組(L(S), P(S), {(l, p)(p, l)I(S)})Sの双対構造という。
これをSと表記する。

双対構造も同様に次が成り立つ。

(S)=Sが成り立つ。

そして、双対構造も結合行列で定義できる。

双対構造(結合行列を用いた定義)

Sを結合構造とする。
このとき結合行列B(S)の転置行列tB(S)を接続行列として持つ結合構造をSの双対構造という。

こちらの定義の同値性も自明である。

元の構造のクラス次第では補構造や双対構造は同じクラスになるので調べるのに便利な時がしばしば存在する。

よく使われる調べ方

補構造や双対構造以外にもよく使われる調べ方が他にもある。

ある種の正則条件の設定

先ほど出てきた扱いやすいクラスを得るための条件である、ある種の正則条件の設定である。

線形幾何(linear space, Wikipedia(EN))

「任意の異なる二点を通る直線はただ一つ」と「任意の直線は二つ以上の点からなる」、「直線が二本以上存在する」という条件を結合構造が満たすとき、その結合構造を線形幾何という。

ブロックデザイン(block design, Wikipedia)

ここでは直線をブロックと呼ぶことにする。
v>k>tとなる正整数 t, v, k, λに対して「点の数はv個である。」、「各ブロックに含まれる点の数はk個である。」、「任意の相異なるt個の点に対してそれらを含むブロックの個数はλ個であり、そのブロックの個数はt個の点の取り方によらない。」を結合構造が満たすとき、その結合構造はt-(v, k, λ)デザインという。
なお、2-(v, 2, λ)は無向グラフとしても見ることができる。

準同型写像

SSを結合構造とする。f=(fP, fL)が次の三つの条件を満たしているとき、fSからSへの準同型写像という。

  1. fPP(S)からP(S)への写像である。
  2. fLL(S)からL(S)への写像である。
  3. (A, l)I(S)(fP(A), fL(l))I(S)

一般的な準同型の定義と同様に逆写像、同型も定義される。また、有限で単純な結合構造から自身への自己同型写像のとき自己同型群を置換群とみることで、置換群の旗集合に対して結合構造への置換群による作用が定義できる。同様にして結合構造への群の作用も定義できる。(これらの定義を紹介すると長くなりすぎるのでここでは説明しない。)

おわりに

今回は結合構造の利用については解説していないが、今後どこかで書くと思う。

以上です。

参考文献

[1]
坂内 英一, 坂内 悦子, 伊藤 達郎, 代数的組合せ論入門, 共立出版, 2016
[2]
ヴァン・リントン、ウィルソン, 組合せ論 上, 丸善出版, 2018
[3]
Gyorgy Kiss, Tamas Szonyi, Finite Geometries, Chapman and Hall/CRC, 2019
[4]
ヴァン・リントン、ウィルソン, 組合せ論 下, 丸善出版, 2019
投稿日:20211211
OptHub AI Competition

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。
バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

ogata_k
ogata_k
10
1350
興味の赴くまま数学をやってます。 (有向・無向・ハイパー)グラフが好きです。

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中
  1. 結合構造とは
  2. 結合構造(接続構造)
  3. 部分集合との同一視
  4. 結合構造の例
  5. 構造から構造の生成
  6. よく使われる調べ方
  7. おわりに
  8. 参考文献