ハッセ図 ハッセ図の概要

ウィキペディア

ハッセ図

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/08/30 10:11 UTC 版)

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

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

例

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

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

• 集合 { 1, 2, 3, 4 } には全部で15の分割があり、細分 (refinement) による半順序があり（より細かい分割の方が小さいとする）、次のようなハッセ図で表される。

Bruhat order

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

動機

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

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

• a ≤ a （反射律）
• a ≤ b かつ b ≤ c なら a ≤ c （推移律）
• a ≤ b かつ b ≤ a なら a = b （反対称律）

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

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

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

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

被覆関係

記号的には、ハッセ図の全ての辺は x < y という関係の (x, y) の形であり（上述したようにループを排除するため条件が厳しくなっている）、x < z < y となるような z は存在しない（推移律による辺を除外するためのもう1つの規則）。

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

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