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

半順序集合は 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

ホモトピー論の視点からは, ポセットを 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) は, ポセットの不変量であるが, 他にも様々な不変量が考えられている。

• Eulerian posetに対するtoric polynomial (Stanley [Sta87])
• Hetyei [Het13]のshort toric polynomial
• order polynomial [Sta70]
• order polytope と chain polytope (Stanley [Sta86])
• Ardila と Bliem と Salazar [ABS11] の marked order polytopes と marked chain polytopes

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

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

ポセットに対して次元を定義することもできる。元々 Dushnik と Miller が [DM41] で定義したものであるが, その後, Novák [Nov63] により自然数 \(k\) に対し \(k\)-dimension という概念に拡張され ている。

• ポセットの次元

\(2\)次元のものについて, finite \(T_0\)-space のトポロジーを用いて調べているの は, Barmak と Minian [BM07] である。

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

• lattice

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

• poset limit

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

References

[ABS11]

Federico Ardila, Thomas Bliem, and Dido Salazar. “Gelfand-Tsetlin polytopes and Feigin-Fourier-Littelmann-Vinberg polytopes as marked poset polytopes”. In: J. Combin. Theory Ser. A 118.8 (2011), pp. 2454–2462. arXiv: 1008.2365. url: http://dx.doi.org/10.1016/j.jcta.2011.06.004.

[Bjö95]

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

[BM07]

Jonathan Ariel Barmak and Elias Gabriel Minian. “2-dimension from the topological viewpoint”. In: Order 24.1 (2007), pp. 49–58. arXiv: math/0702198. url: http://dx.doi.org/10.1007/s11083-007-9057-1.

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

[DM41]

Ben Dushnik and E. W. Miller. “Partially ordered sets”. In: Amer. J. Math. 63 (1941), pp. 600–610. url: https://doi.org/10.2307/2371374.

[Het13]

Gábor Hetyei. “The short toric polynomial”. In: Trans. Amer. Math. Soc. 365.3 (2013), pp. 1441–1468. arXiv: 1008.4433. url: http://dx.doi.org/10.1090/S0002-9947-2012-05659-5.

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

[Nov63]

Vı́tězslav Novák. “On the pseudodimension of ordered sets”. In: Czechoslovak Math. J. 13 (88) (1963), pp. 587–598.

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

[Sta70]

Richard P. Stanley. “A chromatic-like polynomial for ordered sets”. In: Proc. Second Chapel Hill Conf. on Combinatorial Mathematics and its Applications (Univ. North Carolina, Chapel Hill, N.C., 1970). Univ. North Carolina, Chapel Hill, N.C., 1970, pp. 421–427.

[Sta86]

Richard P. Stanley. “Two poset polytopes”. In: Discrete Comput. Geom. 1.1 (1986), pp. 9–23. url: http://dx.doi.org/10.1007/BF02187680.

[Sta87]

Richard Stanley. “Generalized \(H\)-vectors, intersection cohomology of toric varieties, and related results”. In: Commutative algebra and combinatorics (Kyoto, 1985). Vol. 11. Adv. Stud. Pure Math. Amsterdam: North-Holland, 1987, pp. 187–213.

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