Invariants of Posets

トポロジーの視点からは, poset の不変量としては, まず order complex と呼ばれる simplicial complex を挙げるべきだろう。 小圏とみなして, 分類空間を取ったものであるが。 組み合せ論の問題をトポロジーの道具で考える topological combinatorics の基本的な道具である。

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

関連したものとして, Möbius 関数がある。 G.-C. Rota により [Rot64]で定義されたものであるが, Leinster [Lei08] により小圏に一般化されている。

• Möbius 関数と組み合せ論的に定義された Euler 標数

Poset からは, 様々な 多面体が構成される。

• order polytope と chain polytope (Stanley [Sta86])
• Ardila と Bliem と Salazar [ABS11] の marked order polytope と marked chain polytope
• maximal chain polytope
• order-chain polytope [Hib+19]
• marked chain-order polytope [FF16]
• enriched order polytope と enriched chain polytope [OT21]
• partial order polytope [Fio03]
• linear order polytope [AA63; BM81; GJR85]
• relative poset polytope [FM24]
• poset associahedron [Gal24]

Simplicial complex としては, 例えば Scarf complex [McG] がある。

Poset を図式で表す方法として Hasse diagram があるが, これは poset の quiver に値を持つ不変量と考えることができる。Poset の表示とみなすべきだが。 他にも incomparability graph というものがある。

• Hasse diagram
• incomparability graph

より不変量らしいものとしては, 数や多項式に値を持つ不変量がある。

Ehrenborg と Readdy [ER20] によると Eulerian poset については, cd-index は重要な不変量である。Survey として Bayer の [Bay21] がある。

• cd-index

次元も色々定義されている。

• Dushnik-Miller dimension [DM41]
• Ore dimension [Ore67]
• Boolean dimension [NP89]
• well dimension [Nov69]
• geometric dimension [HBG]
• Debreu dimension [HBG]

Haiman [Hai24] は, Dushnik-Miller dimension については, Trotter の本 [Tro92] を参照している。

多項式不変量としては, 次のようなものがある。

• characteristic polynomial
• Eulerian poset に対する toric polynomial (Stanley [Sta87])
• Hetyei [Het13] の short toric polynomial
• order polynomial [Sta70]
• Chapoton [Cha18] の4変数多項式

代数的不変量としては, 以下のものがある。

• incidence algebra and incidence coalgebra
• Lie poset algebra
• splitting algebra [KS15]
• toggle group [CF95]

Lie poset algebra は, incidence algebra の conunit の kernel として定義される incidence algebra を commutator により Lie algebra と思ったものの Lie subalgebra である。 Coll と Gerstenhaber により [CG16] で導入された。 最近 Coll らによって [CM21a], [CM21b], [Cam+23], [MR23], [CMR22] などで調べられている。

References

[AA63]

F. J. Anscombe and R. J. Aumann. “A definition of subjective probability”. In: Ann. Math. Statist. 34 (1963), pp. 199–205. url: https://doi.org/10.1214/aoms/1177704255.

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

[Bay21]

Margaret M. Bayer. “The \(cd\)-index: a survey”. In: Polytopes and discrete geometry. Vol. 764. Contemp. Math. Amer. Math. Soc., [Providence], RI, [2021] ©2021, pp. 1–19. arXiv: 1901.04939. url: https://doi.org/10.1090/conm/764/15355.

[BM81]

Jean-Pierre Barthélémy and Bernard Monjardet. “The median procedure in cluster analysis and social choice theory”. In: Math. Social Sci. 1.3 (1980/81), pp. 235–267. url: https://doi.org/10.1016/0165-4896(81)90041-X.

[Cam+23]

Alex Cameron, Vincent E. Coll Jr., Nicholas Mayers, and Nicholas Russoniello. “The breadth of Lie poset algebras”. In: Linear Multilinear Algebra 71.16 (2023), pp. 2565–2584. arXiv: 2105.02429. url: https://doi.org/10.1080/03081087.2022.2111545.

[CF95]

P. J. Cameron and D. G. Fon-Der-Flaass. “Orbits of antichains revisited”. In: European J. Combin. 16.6 (1995), pp. 545–554. url: https://doi.org/10.1016/0195-6698(95)90036-5.

[CG16]

Vincent E. Coll Jr. and Murray Gerstenhaber. “Cohomology of Lie semidirect products and poset algebras”. In: J. Lie Theory 26.1 (2016), pp. 79–95. arXiv: 1407.0428.

[Cha18]

Frédéric Chapoton. “Une note sur les intervalles de Tamari”. In: Ann. Math. Blaise Pascal 25.2 (2018), pp. 299–314. arXiv: 1711.05027. url: http://ambp.cedram.org/item?id=AMBP_2018__25_2_299_0.

[CM21a]

Vincent E. Coll Jr. and Nicholas W. Mayers. “The index of Lie poset algebras”. In: J. Combin. Theory Ser. A 177 (2021), Paper No. 105331, 34. arXiv: 1908.06573. url: https://doi.org/10.1016/j.jcta.2020.105331.

[CM21b]

Vincent E. Coll Jr. and Nicholas W. Mayers. “Toral posets and the binary spectrum property”. In: J. Algebraic Combin. 54.4 (2021), pp. 1065–1093. url: https://doi.org/10.1007/s10801-021-01038-6.

[CMR22]

Vincent E. Coll Jr., Nicholas W. Mayers, and Nicholas Russoniello. “Contact Lie poset algebras”. In: Electron. J. Combin. 29.3 (2022), Paper No. 3.35, 22. url: https://doi.org/10.37236/10821.

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

[ER20]

Richard Ehrenborg and Margaret Readdy. “Balanced and Bruhat graphs”. In: Ann. Comb. 24.3 (2020), pp. 587–617. arXiv: 1304.1169. url: https://doi.org/10.1007/s00026-020-00510-7.

[FF16]

Xin Fang and Ghislain Fourier. “Marked chain-order polytopes”. In: European J. Combin. 58 (2016), pp. 267–282. arXiv: 1508.02232. url: https://doi.org/10.1016/j.ejc.2016.06.007.

[Fio03]

Samuel Fiorini. “A combinatorial study of partial order polytopes”. In: European J. Combin. 24.2 (2003), pp. 149–159. url: https://doi.org/10.1016/S0195-6698(03)00009-X.

[FM24]

Evgeny Feigin and Igor Makhlin. “Relative poset polytopes and semitoric degenerations”. In: Selecta Math. (N.S.) 30.3 (2024), Paper No. 48. arXiv: 2112.05894. url: https://doi.org/10.1007/s00029-024-00935-5.

[Gal24]

Pavel Galashin. “\(P\)-associahedra”. In: Selecta Math. (N.S.) 30.1 (2024), Paper No. 6. arXiv: 2110.07257. url: https://doi.org/10.1007/s00029-023-00896-1.

[GJR85]

Martin Grötschel, Michael Jünger, and Gerhard Reinelt. “Facets of the linear ordering polytope”. In: Math. Programming 33.1 (1985), pp. 43–60. url: https://doi.org/10.1007/BF01582010.

[Hai24]

Milan Haiman. “The dimension of divisibility orders and multiset posets”. In: Order 41.3 (2024), pp. 693–707. arXiv: 2201.12952. url: https://doi.org/10.1007/s11083-023-09653-7.

[HBG]

Pedro Hack, Daniel A. Braun, and Sebastian Gottwald. On a geometrical notion of dimension for partially ordered sets. arXiv: 2203.16272.

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

[Hib+19]

Takayuki Hibi, Nan Li, Teresa Xueshan Li, Li Li Mu, and Akiyoshi Tsuchiya. “Order-chain polytopes”. In: Ars Math. Contemp. 16.2 (2019), pp. 299–317. arXiv: 1504.01706. url: https://doi.org/10.26493/1855-3974.1164.2f7.

[KS15]

Tyler Kloefkorn and Brad Shelton. “Splitting algebras: Koszul, Cohen-Macaulay and numerically Koszul”. In: J. Algebra 422 (2015), pp. 660–682. arXiv: 1207.1330. url: https://doi.org/10.1016/j.jalgebra.2014.08.050.

[Lei08]

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

[McG]

Trevor McGuire. A Preliminary Report on Scarf Complexes of Posets. arXiv: 1410.2074.

[MR23]

Nicholas W. Mayers and Nicholas Russoniello. “On toral posets and contact Lie algebras”. In: J. Geom. Phys. 190 (2023), Paper No. 104861, 27. arXiv: 2208.09060. url: https://doi.org/10.1016/j.geomphys.2023.104861.

[Nov69]

Vítězslav Novák. “On the well dimension of ordered sets”. In: Czechoslovak Math. J. 19(94) (1969), pp. 1–16.

[NP89]

J. Nešetřil and P. Pudlák. “A note on Boolean dimension of posets”. In: Irregularities of partitions (Fertőd, 1986). Vol. 8. Algorithms Combin. Study Res. Texts. Springer, Berlin, 1989, pp. 137–140.

[Ore67]

Oystein Ore. Theory of graphs. American Mathematical Society Colloquium Publications, Vol. XXXVIII. Third printing, with corrections. American Mathematical Society, Providence, RI, 1967, pp. x+270.

[OT21]

Hidefumi Ohsugi and Akiyoshi Tsuchiya. “Enriched order polytopes and enriched Hibi rings”. In: Eur. J. Math. 7.1 (2021), pp. 48–68. arXiv: 1903.00909. url: https://doi.org/10.1007/s40879-020-00403-2.

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

[Tro92]

William T. Trotter. Combinatorics and partially ordered sets. Johns Hopkins Series in the Mathematical Sciences. Dimension theory. Johns Hopkins University Press, Baltimore, MD, 1992, pp. xvi+307. isbn: 0-8018-4425-8.