組み合せ論的データとしてのポセット

半順序集合は partially ordered set の略として poset と呼ばれることが多い。 日本語だと順序集合とか半順序集合とかあいまいなので, ここでも以下ポセットと呼ぶことにする。 組み合せ論での重要な研究対象である。

例としては以下のようなものがある。

• 凸多面体, simplicial complex, hyperplane arrangementなどの face poset
• 有限群の部分群の成す poset
• partition poset
• 位相

位相の中でも, 可換環 \(R\) の \(\mathrm {Spec}(R)\) の位相は特殊なので, その特徴付けも考えられている。Hochster の [Hoc69] や Lewis の [Lew73] など。

他にも, 組み合せ論的データから様々なポセットができる。

Brady と McCammond の [BM10] では, Björner の [Bjö95] と Stanley の [Sta97] が, 基本的な文献として挙げられている。

組み合せ論的な問題から現われるポセットのclassとして以下のようなものがある。

• graded poset
• Eulerian poset
• triangular poset
• binomial poset
• Sheffer poset
• thin poset

ホモトピー論の視点からは, ポセットを small category とみなす方が分類空間の理論と結び付くのでよいように思う。 その視点からは, ポセットより preordered set という概念の方が基本的に思える。

• poset を small category とみなすこと
• preordered set の定義

このように見ると, ポセットに関する定義や性質で small category に一般化できるものは少なくない。Leinster は, [Lei08] で small category に対する Möbius 関数を定義している。 ポセットの Möbius 関数は, G.-C. Rota により [Rot64]で定義されたもののようである。

• Möbius関数

Small category に対しては, その分類空間が構成できる。 ポセットの分類空間の性質については, [Qui78]の§1を見るとよい。 このように, ポセットをその分類空間を通してトポロジーの道具で調べるのは, 重要な手法である。

• ポセットのホモトピー論
• topological combinatorics

Möbius関数や分類空間 (order complex) は, ポセットの不変量であるが, 他にも様々な不変量が考えられている。

• invariants of posets

ポセットには自然に位相が入り, \(T_0\)空間とみなすことができる。実は finite poset の圏と finite \(T_0\)空間の圏は同じものである。また \(T_0\) 空間上の層と対応するポセット上の contravariant functor, つまり incidence algebra 上の module を同一視することができる。

• finite \(T_0\)-space
• ポセット上の層
• incidence algebra

順序集合に, その有限部分集合の sup と inf を取る操作が加わったものを lattice という。組み合せ論では基本的な概念である。

• lattice

Posetに対する操作も色々あるが, ホモトピー論との関係では, poset の図式, すなわち poset の category に値を持つ presheaf や precosheaf に対する Grothendieck construction が重要である。組み合せ論の世界では poset limit と呼ばれているようであるが。

• diagram of posets
• poset limit

Ladkani は [Lad] で flip-flop という poset の間の関係を導入している。

References

[Bjö95]

A. Björner. “Topological methods”. In: Handbook of combinatorics, Vol. 1, 2. Amsterdam: Elsevier, 1995, pp. 1819–1872.

[BM10]

Tom Brady and Jon McCammond. “Braids, posets and orthoschemes”. In: Algebr. Geom. Topol. 10.4 (2010), pp. 2277–2314. arXiv: 0909. 4778. url: http://dx.doi.org/10.2140/agt.2010.10.2277.

[Hoc69]

M. Hochster. “Prime ideal structure in commutative rings”. In: Trans. Amer. Math. Soc. 142 (1969), pp. 43–60. url: https://doi.org/10.2307/1995344.

[Lad]

Sefi Ladkani. Universal derived equivalences of posets of tilting modules. arXiv: 0708.1287.

[Lei08]

Tom Leinster. “The Euler characteristic of a category”. In: Doc. Math. 13 (2008), pp. 21–49. arXiv: math/0610260.

[Lew73]

William J. Lewis. “The spectrum of a ring as a partially ordered set”. In: J. Algebra 25 (1973), pp. 419–434.

[Qui78]

Daniel Quillen. “Homotopy properties of the poset of nontrivial \(p\)-subgroups of a group”. In: Adv. in Math. 28.2 (1978), pp. 101–128. url: http://dx.doi.org/10.1016/0001-8708(78)90058-0.

[Rot64]

Gian-Carlo Rota. “On the foundations of combinatorial theory. I. Theory of Möbius functions”. In: Z. Wahrscheinlichkeitstheorie und Verw. Gebiete 2 (1964), 340–368 (1964).

[Sta97]

Richard P. Stanley. Enumerative combinatorics. Vol. 1. Vol. 49. Cambridge Studies in Advanced Mathematics. With a foreword by Gian-Carlo Rota, Corrected reprint of the 1986 original. Cambridge: Cambridge University Press, 1997, pp. xii+325. isbn: 0-521-55309-1; 0-521-66351-2.