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

半順序集合は partially ordered set の略として 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を見るとよい。 このように, ポセットをその分類空間を通してトポロジーの道具で調べるのは, 重要な手法である。

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

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

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

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

  • diagram of posets
  • poset limit

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

Poset の変種としては, Reiner [Rei93] による signed poset がある。

  • signed poset

ある条件をみたす\(A\)型のルート系と poset の間に1対1の対応があることから, \(B\)型のルート系を用いて定義されたものである。Reiner は poset に関するいくつかの概念が signed poset に一般化できることを示している。

最近では, chain polytope や order polytope の signed 版が Beck と Hlavacek [BH] により定義されている。

References

[BH]

Matthias Beck and Max Hlavacek. Signed Poset Polytopes. arXiv: 2311.04409.

[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.

[Rei93]

Victor Reiner. “Signed posets”. In: J. Combin. Theory Ser. A 62.2 (1993), pp. 324–360. url: https://doi.org/10.1016/0097-3165(93)90052-A.

[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.