ハッセ図

ハッセ図は、数学における有限半順序集合を単純に図示する方法のひとつで、半順序の推移簡約を描いたものである。具体的には有限半順序集合  があるとき、//S// の個々の元を頂点とし、//x// < //y// で、かつ //x// < //z// < //y// となるような //z// が存在しない場合にのみ //x// から //y// に上向きの線を描く。 この場合、「 //y// は //x// を被覆関係する」または「 //y// は //x// の immediate successorである」というBirkhoff。さらに、各辺が両端の頂点以外を通らないように頂点を配置する必要がある。このような図は半順序を一意に特定し、任意の有限な半順序では推移簡約が一意に定まる。ただし、図における元の配置の仕方は様々なものが考えられ、ひとつの順序集合に対して見た目の異なるハッセ図が多数存在することになる。

ハッセ図はドイツの数論学者ヘルムート・ハッセに因んで名付けられている。これはハッセが部分体や拡大体がなす半順序集合を図示するために効果的に活用したからである。しかし、ハッセが最初にこの図を使ったわけではなく、少なくとも Vogt では既にこの図が使われているBirkhoff。ハッセ図は半順序集合を手で図示する技法として生まれたが、最近ではグラフ描画技法を使って自動的に描くことができる。

「ハッセ図」という言葉は、個々のグラフの描画とは関係なく、抽象概念としての有向非循環グラフの推移簡約を指すこともある。ただし、本項目ではこの意味では使わない。

1. 例
----

{ //x//, //y//, //z// } の冪集合には包含による半順序があり、次のようなハッセ図で表される。

60の全約数の集合 //A// = { 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60 } には、整除性による半順序があり、次のようなハッセ図で表される。

集合 { 1, 2, 3, 4 } には全部で15の分割があり、細分  による半順序があり、次のようなハッセ図で表される。

1.1. Bruhat order
-----------------

全てのコクセター群  にはいくつかの半順序があり、これらをまとめて Bruhat order と呼ぶ。それらの定義は、生成系 //S// における被約語  に基づく。強い Bruhat order において、元 //w// が元 //y// より大きいとは、//y// の被約語をプレフィックスとする //w// の被約語が存在する場合である。この順序についてのハッセ図は  のケイリーグラフと一致する。対称群 //S////n// の場合、ケイリーグラフは置換多面体である。//n//=3 なら、ハッセ図は1つの頂点が一番上にあり、1つの頂点が一番下にある六角形となる。

2. 動機
-----

半順序集合  を視覚的に表現しようとした場合、どうすればよいだろうか? まず S の個々の元を頂点するグラフを描き、//u// ≤ //v// という関係をグラフ内の辺  で表すとする。

このようにしてグラフを描いてみると、非常に混みあったグラフになる。実際、そのグラフには冗長な情報が多すぎる。半順序の必要条件は次の通りである。

//a// ≤ //a//
//a// ≤ //b// かつ //b// ≤ //c// なら //a// ≤ //c//
//a// ≤ //b// かつ //b// ≤ //a// なら //a// = //b// さて、元々のグラフを考えてみると、まず //u// ≤ //u// という反射律が成り立つことから、ノード毎に  というループが存在する。

そこで、より細かい集合の分割がより小さいとする半順序集合  についてループを除外したグラフを作る。すると次のようなグラフが得られる。

しかし、このグラフでも冗長な情報がまだ存在する。半順序の必要条件には、推移律がある。上のグラフでは 、、 という辺が描かれている。この場合  という辺は他の2つの辺から存在を推測できるため、描く必要はない。

以上から、推移関係と反射関係を考慮して残った関係だけを辺として描く。すると、「例」の節の3つ目の図が得られる。

3. 被覆関係
-------

記号的には、ハッセ図の全ての辺は //x// < //y// という関係の  の形であり、//x// < //z// < //y// となるような //z// は存在しない。

この関係を「被覆関係」と呼び、ハッセ図はこの関係を使って定義されることが多い。半順序は、被覆関係の推移閉包である。

したがって //S// のハッセ図は、//y// が //x// を被覆するような全ての順序対  の集合と定義することもできる。すなわち、ハッセ図は被覆関係の逆で識別することもできる。

4. 「よい」ハッセ図
-----------

ハッセ図は有限な半順序集合を扱う単純で直観的なツールであるが、「よい」図を描くのはやや難しい。実際、与えられた半順序集合についてハッセ図はいろんな形で描くことができる。単純な技法としては、最も小さい元を出発点として徐々に大きい方に向かって描いていくという方法があるが、これで生成される図はあまりよいとは言えず、対称性や順序の内部構造が容易に失われてしまう。

ここでは、集合 //S// = {//a//, //b//, //c//, //d//} の冪集合を例として考える。すなわち、//S// のあらゆる部分集合の集合 である。冪集合は部分集合の包含関係 で容易に順序付けできる。この順序を描いた3種類のハッセ図を以下に示す。

左端の図は最も単純な描き方をした場合に近い。5層になっていて、各層にある頂点は、元の数が等しい部分集合に対応している。下から2層目は元が1つの集合に対応するが、個々の頂点にどれを具体的に割り当てるかは様々な組合せがあるものの、これらを具体的に割り当てるとそれより上の層は自動的に固定される。図の複数の頂点のラベル付けをどのようにしても元の半順序が表せるため、これは自己同型の例でもある。

上の例は同じ順序についての異なるハッセ図を示しており、それぞれが元となる数学的構造の異なる面を反映している。左端の図は頂点の層ごとに元の数が対応している。右端の図はその構造の内部対称性を強く反映している。最後に真ん中の図は2つの立方体を繋いだような形になっており、冪集合 2//S// と product order 2 × 2{//a//, //b//, //c//} の間の関係を強調したものとなっている。

よりよい図を描くための様々なアルゴリズムが考案されているが、今のところよい図を描くには人間が介在した方がよい。もっとも、その人間もハッセ図を描くには一種の技量を必要とする。

5. ポリトープ
--------

ハッセ図はポリトープの組合せ的構造を図示するのに非常に役立つ。抽象ポリトープ論においては、ハッセ図こそがポリトープである。

6. 脚注・出典
--------

7. 参考文献
-------

first=Garrett .
first=Garrett.
first1=G. .
first=Ralph . 詳しいプレプリントがオンラインで入手可能: [1].
first=Henri Gustav .

8. 関連項目
-------

束論

9. 外部リンク
--------

[2]
[3] 
[4]
[5]