ハッセ図
ハッセ図（ハッセず、英: Hasse diagram）は、数学における有限半順序集合を単純に図示する方法のひとつで、半順序の推移簡約を描いたものである。具体的には有限半順序集合 (S, ≤) があるとき、S の個々の元を頂点とし、x < y で、かつ x < z < y となるような z が存在しない場合にのみ x から y に上向きの線（辺）を描く（ここで二項関係 < は全ての x について (x, x) という元を ≤ から除くことで得られる）。 この場合、「 y は x を被覆する」または「 y は x の immediate successor（直接の後続）である」という[1]。さらに、各辺が両端の頂点以外を通らないように頂点を配置する必要がある。このような図（頂点にはラベルが付属するものとする）は半順序を一意に特定し、任意の有限な半順序では推移簡約が一意に定まる[2]。ただし、図における元の配置の仕方は様々なものが考えられ、ひとつの順序集合に対して見た目の異なるハッセ図が多数存在することになる。
ハッセ図はドイツの数論学者ヘルムート・ハッセ（1898年–1979年）に因んで名付けられている。これはハッセが部分体や拡大体がなす半順序集合を図示するために効果的に活用したからである[3]。しかし、ハッセが最初にこの図を使ったわけではなく、少なくとも Vogt (1895) では既にこの図が使われている[4]。ハッセ図は半順序集合を手で図示する技法として生まれたが、最近ではグラフ描画技法を使って自動的に描くことができる[5]。
「ハッセ図」という言葉は、個々のグラフの描画とは関係なく、抽象概念としての有向非循環グラフの推移簡約を指すこともある。ただし、本項目ではこの意味では使わない。
Contents
例
- 集合 { 1, 2, 3, 4 } には全部で15の分割があり、細分 (refinement) による半順序があり（より細かい分割の方が小さいとする）、次のようなハッセ図で表される。
Bruhat order
全てのコクセター群 (W, S) にはいくつかの半順序があり、これらをまとめて Bruhat order と呼ぶ。それらの定義は、生成系 S における被約語 (reduced word) に基づく。強い Bruhat order において、元 w が元 y より大きいとは、y の被約語をプレフィックスとする w の被約語が存在する場合である。この順序についてのハッセ図は (W, S) のケイリーグラフと一致する。対称群 Sn の場合、ケイリーグラフは置換多面体である。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) の集合と定義することもできる。すなわち、ハッセ図は被覆関係の逆で識別することもできる。
「よい」ハッセ図
ハッセ図は有限な半順序集合を扱う単純で直観的なツールであるが、「よい」図を描くのはやや難しい。実際、与えられた半順序集合についてハッセ図はいろんな形で描くことができる。単純な技法としては、最も小さい元を出発点として徐々に大きい方に向かって描いていくという方法があるが、これで生成される図はあまりよいとは言えず、対称性や順序の内部構造が容易に失われてしまう。
ここでは、集合 S = {a, b, c, d} の冪集合を例として考える。すなわち、S のあらゆる部分集合の集合 [math]\mathcal{P}(S)[/math] である。冪集合は部分集合の包含関係 [math]\subseteq[/math] で容易に順序付けできる。この順序を描いた3種類のハッセ図を以下に示す。
| ファイル:Hypercubeorder binary.svg | ファイル:Hypercubecubes binary.svg | ファイル:Hypercubestar binary.svg |
左端の図は最も単純な描き方をした場合に近い。5層になっていて、各層にある頂点は、元の数が等しい部分集合に対応している。下から2層目は元が1つの集合に対応するが、個々の頂点にどれを具体的に割り当てるかは様々な組合せがあるものの、これらを具体的に割り当てるとそれより上の層は自動的に固定される。図の複数の頂点のラベル付けをどのようにしても元の半順序が表せるため、これは自己同型の例でもある（特に断らない限り、辞書式順序を仮定することが推奨される）。
上の例は同じ順序についての異なるハッセ図を示しており、それぞれが元となる数学的構造の異なる面を反映している。左端の図は頂点の層ごとに元の数が対応している。右端の図はその構造の内部対称性を強く反映している。最後に真ん中の図は2つの立方体を繋いだような形になっており、冪集合 2S と product order 2 × 2{a, b, c} の間の関係を強調したものとなっている。
よりよい図を描くための様々なアルゴリズムが考案されているが、今のところよい図を描くには人間が介在した方がよい。もっとも、その人間もハッセ図を描くには一種の技量を必要とする。
ポリトープ
ハッセ図はポリトープの組合せ的構造（頂点、辺、面などの階層）を図示するのに非常に役立つ。抽象ポリトープ論においては、ハッセ図（より正確には半順序集合）こそがポリトープである。
脚注・出典
- ↑ Birkhoff 1967, p. テンプレート:Google books quote.
- ↑ 無限な半順序は推移簡約を持つとは限らない。各元には必ず immediate successor がなければならない。実数の区間 [0, 1] を考えてみればよい。
- ↑ Birkhoff (1948, p. 6)とSchröder (2016, p. テンプレート:Google books quote)を参照。
- ↑ Birkhoff 1948, p. 6.
- ↑ 例えば、Di Battista & Tamassia (1988) や Freese (2004) を参照
参考文献
- Birkhoff, Garrett (1948), Lattice Theory, American Mathematical Society Colloquium Publications, 25 (Revised ed.), American Mathematical Society, MR 0029876, Zbl 0033.10103.
- Birkhoff, Garrett (1967), Lattice Theory, American Mathematical Society Colloquium Publications, 25 (Third ed.), American Mathematical Society, MR 0227053, Zbl 0153.02501.
- Di Battista, G.; Tamassia, R. (1988), “Algorithms for plane representation of acyclic digraphs”, Theoretical Computer Science 61: 175–178.
- Freese, Ralph (2004), “Automated lattice drawing”, Concept Lattices, Lecture Notes in Computer Science, 2961, Springer-Verlag, pp. 589–590. 詳しいプレプリントがオンラインで入手可能: [1].
- Schröder, B. (2016), Ordered Sets: An Introduction with Connections from Combinatorics to Topology (Second ed.), Birkhäuser, ISBN 978-3-319-29786-6, MR 3469976, Zbl 06560023
- Vogt, Henri Gustav (1895), Leçons sur la résolution algébrique des équations, Nony, p. 91.