【組合せ論】メビウスの反転公式2　「 Poset における incidence algebra(隣接代数)」

本格的にposetでのメビウス反転公式に向けての準備を始めていきます。

今回はposetの定義および poset 上の incidence algebra (隣接代数)の定義を行います。

※証明は最小限にとどめていますので、何かあればご連絡ください。

(前回は、古典的なメビウスの反転公式について軽く触れました。)

math-topology.hatenablog.com

定義と具体例
Locally finite poset
Incidence algebra(隣接代数)とConvolution
補足(本筋から外れること)
参考文献
まとめ
次の記事

定義と具体例

定義1(Poset)

集合 $P$ 上に二項関係 $\le$ が定義され、以下の性質を満たすとき、 $P$ または $(P,\le)$ は poset (半順序集合、partially orderd set) であるという。

$P$ の任意の元 $x$ , $y$ , $z$ に関して

(1)(反射律)　　 $x\le x$

(2)(推移律)　　 $x\le y$ かつ $y\le z$ ならば $x\le z$

(3)(反対称律)　 $x\le y$ かつ $y\le x$ ならば $x=y$

( $x=y$ は集合の元として等しいことを意味します。)

なお、 $P$ の元 $x$ , $y$ に関して、

$x\le y$ かつ $x\ne y$ のとき $x\lt y$ と書くこととする。

どのあたりが「半」順序なのか、にも触れておきます。たとえば $\mathbb{R}$ (実数全体の集合) の任意の元には大小関係が定まります。これを全順序律と呼ぶのですが、poset にはこの性質は要求しません。

つまり「比べられないものがあってもOK」ということになります。

さて定義を言っただけではイメージが湧きませんので具体例を挙げていきましょう。

例1(自然数と大小関係)

$\mathbb{N}$ を $1$ 以上からなる自然数の集合と定義します。

通常の大小関係により、これはposetとなります。*2

例2(自然数と約数)

例1の $\mathbb{N}$ の元 $a$ と $b$ に対して、 $a$ が $b$ の約数であるときに、 $a|b$ と表すこととすると、二項関係 $|$ に関しても $\mathbb{N}$ は poset となります。なお、全順序律は満たしません。

このように同じ集合においても二項関係の入れ方により異なる poset を作れます。

例3(実数と大小関係)

任意の実数からなる集合 $\mathbb{R}$ は例1と同じく通常の大小関係により poset となります。

例4(冪集合)

有限集合 $A$ について $A$ の冪集合、すなわち $A$ の任意の部分集合を元に持つ集合を $2^{A}$ と書きます。

このとき「集合の包含関係」により $2^{A}$ は poset となります。

例5(3次元凸多面体)*3

中身がつまっていない3次元多面体 $K$ について、 $K$ の頂点の集合 $A$ とすると、冪集合(例4) $2^{A}$ の元は、空集合以外は多面体の頂点、辺、面、全体 $K$ と1:1に対応します。

よって多面体 $K$ の頂点、辺、面、 $K$ 自身の集まりは $2^{A}$ と同一視することで例4の poset の構造が入ります。

Locally finite poset

さて今後、poset に対して写像を考えていくのですが、その場合、有限集合であると嬉しいのですが、もちろんそんなわけにもいきません。

なぜなら古典的なメビウス反転公式を思い出したとき例2のように、自然数全体という無限集合に対してメビウス関数を定義しているからです。

そこで、有限集合よりは弱い概念ですが写像を定義するうえで重要な役割を果たす locally finite poset というものを導入します。

定義2(Interval)

Poset $P$ の元 $x$ , $y$ が $x\le y$ を満たすとき、

$[x , y]=\{ z\in P \,|\, x\le z\le y \}$ の形で与えられる $P$ の部分集合を、

$P$ の interval と呼ぶ。

定義3(Locally finite poset)

Poset $P$ の任意の interval が有限集合になるとき、 $P$ は locally finite poset という。 $P$ が有限集合であれば $P$ は特に locally finite posetとなる。

先ほどの具体例に関して見ていきましょう。

例1(自然数と大小関係)は有限集合ではありませんが locally finite poset です。

例2(自然数と約数)も同じく有限集合ではありませんが locally finite poset です。

例3(実数と大小関係)は有限集合でも locally finite poset でもありません。

例4(冪集合)は有限集合ですので、特に locally finite poset です。

例5(3次元凸多面体)も例4と同様に、有限集合であり locally finite poset となります。

Incidence algebra(隣接代数)とConvolution

Locally finite poset $P$ の interval の集まりを ${\rm Int}(P)$ と書きます。*5

${\rm Int}(P)$ で定義され、複素数を値にとる単なる写像(関数)

$f: {\rm Int}(P) \longrightarrow \mathbb{C}$ ( $\mathbb{C}$ は複素数の集合 )

からなる集合を $I(P)$ と書くこととします。

また本来、上記の写像 $f$ と interval $[x,y]$ に対して $f([x,y] )$ と書くべきですが、書きづらいので単に $f(x,y)$ と書くこととします。*6

この $I(P)$ を $P$ の incidence algebra (隣接代数) と呼びます。

このネーミングからも $I(P)$ には $\mathbb{C}$ -algebra(多元環)の構造が入ることが予想されますが、積はどのように定義するのでしょうか。

定義4(Convolution)

$P$ を locally finite poset とする。

$f,g\in I(P)$ について convolution $f\ast g\in I(P)$ を以下で定義する。

任意の $P$ の interval $[x ,y]$ に対して、

$(f\ast g)(x,y)=\displaystyle\sum_{x\le z\le y}f(x,z)g(z,y)$ .

$P$ は locally finite poset なので上式の右辺は有限和になる。

Locally finite poset であることが活きていますね。

さて、この convolution に関して以下の性質が成り立ちます。

補題1(Convolution の associativity)

$f,g,h\in I(P)$ について、 $(f\ast g)\ast h =f\ast (g\ast h)$ が成り立つ。

この性質は今後使うことになるのでしっかりと証明しておきましょう。

(証明)

$P$ の interval $[x,y]$ について、

$((f\ast g)\ast h)(x,y)$

$=\displaystyle\sum_{x\le z\le y} ( (f\ast g)(x,z) )h(z,y)$

$=\displaystyle\sum_{x\le w\le z\le y} f(x,w)g(w,z)h(z,y)$

$=\displaystyle\sum_{x\le w\le y} f(x,w) ( (g\ast h)(w,y) )$

$=(f\ast (g\ast h) ) (x,y)$

(すべて有限和をとっています)

となるので証明が終わります。

(証明終わり)

補足(本筋から外れること)

本シリーズにおいては $I(P)$ が $\mathbb{C}$ -algebra であることを使わないので、 $\mathbb{C}$ -algebra の構造に関しては深入りしません。

しかし、上記の命題を使うことで、 convolution を積として associative な $\mathbb{C}$ -algebra であることは簡単に示されます。

$P$ が有限集合である場合には、 $I(P)$ は $\mathbb{C}$ 上の正方行列(もっと言うと上三角行列)で書くことが出来ます。またこの場合、convolution は行列の積に対応するため、自然な書き換えと言えます。

参考文献

[Sta] Richard P. Stanley, Enumerative Combinatorics, Cambridge University Press40 W. 20 St. New York, NYUnited States, 2012.

リンク

まとめ

このままだと少し長くなってしまいそうなので今回は以上になります。

今回は Poset の具体例と諸概念( locally finite poset, incidence algebra, convolution )の導入を行いました。

最後に登場した incidence algebra について次回はさらに深めていきます。

具体的には zeta function (ζ関数) 、そしてその「逆元」として Möbius function (メビウス関数) を与えていきます。

Möbius function の与え方は locally finite ということを存分に生かしているので見どころかもしれません。

それでは最後まで読んでいただきありがとうございました。

次回もなにとぞよろしくお願いします。

math-topology.hatenablog.com

*1:Posetになっているかどうかの証明は省略します。もし気になればコメントしていただけると対応したいと思います。

*2:全順序律も成り立ちます。

*3:高校数学で単に「多面体」と呼ばれるものです。

*4:抽象的に、単体複体や、胞複体など代数トポロジー的な対象に対しても poset の構造を入れられます。

*5: ${\rm Int}(P)$ は有限集合とは限りません。

*6:直積集合 $P\times P$ で定義される写像として拡張することも可能は可能ですが、今回は使いません。あくまで略記したいがためにこのように書きます。

とぽろじい　～大人の数学自由研究～

高校数学から分かる新しい数学、大学で学ぶ数学を少しずつまとめていくブログです。ゆくゆくは本にまとめたいと思っています。