Permutohedron と関連した話題

\(\R ^{n}\) の点 \((1,\ldots ,n)\) の座標の permutation で得られる点達の convex hull で得られる convex polytope \(P_{n}\) を permutohedron という。 Ziegler [Zie95] の本によると, Schoute [Sch11] により, 最初に調べられたようである。

\(\R ^{n}\) 内で定義されているが, 超平面 \[ x_{1}+\cdots +x_n=\frac {n(n+1)}{2} \] に乗っているので, \((n-1)\)次元多面体である。頂点は, \((1,\ldots ,n)\) の permutation \((i_{1},\ldots ,i_{n})\) で得られる \(n!\) 個の点であるが, それを \(\{1,\ldots ,n\}\) の順序の付いた分割 \(i_{1}|\ldots |i_{n}\) とみなすのがよい。 すると, より一般に \(k\) 次元の面は, 集合 \(\{1,\ldots ,n\}\) の \((n-k)\)個への順序の付いた分割と1対1に対応する。 つまり, \(P_{n}\) の face poset は, \(\{1,\ldots ,n\}\) の partition が成す poset \(\Pi _{n}\) の opposite と同型である。

人によっては, permutahedron と書いたりする。 例えば, Loday の [Lod04] では permutohedron であるが, Hohlweg の [Hoh12] では permutahedron と書かれている。 Wikipedia のページ によると, フランス語の permutoédre という用語が, Guilbaud と Rosenstiehl の [GR63] で導入されたのが最初らしい。 ここでは, それにならって permutohedron と綴ることにする。

A. Postnikov [Pos09] は, より一般の点 \((x_{1},\ldots ,x_{n})\) の座標の permutation から得られるもの \(P_{n}(x_{1},\ldots ,x_{n})\) を generalized permutohedron と呼んでいる。

• generalized permutohedron

その体積や lattice point について, Postnikov が [Pos09] で調べている。Postnikov らは, [PRW08] で面の数 (\(f\)-vector) などを決定している。

Aguiar と Ardila [AA] は, generalized permutohedron 達が Hopf monoid in species の構造を持つことを示している。 Ardila と Sanchez [AS] は, その Hopf monoid の構造と valuation の構造が, generalized permutohedron に対しては compatible であることを示している。

変種としては, まず Kapranov [Kap93] により考えられた permutoassociahedron を挙げるべきだろう。 Ivanović ら [BIP19; Iva] による同じ頂点を持つ simple polytope になっているものもある。

• permutoassociahedron
• simple permutoassciahedron

正確には, Kapranov は assciahedron と permutohedron の face poset を合わせたような poset を定義し, それが CW ball の face poset であることを示した。 それが凸多面体の face poset として実現できることを示したのは, Reiner と Ziegler [RZ94] である。Castillo と Liu [CL] による別の実現もある。

Oh [Oh13] は, transversal matroid から convex polytope を構成する方法を考え, できた polytope を transversalhedron と呼んでいる。Generalized permutohedron に関係したもののようである。

別の方向としては, symmetric group が reflection group であることに着目し, Coxeter group に一般化することが考えられている。それについては Hohlweg の survey [Hoh12] がある。

• Coxeter permutohedron

この Hohlweg の survey によると, permutohedron を 単体を切ることにより作る方法を発見したのは, Shnider と Sternberg [SS93] であり, それを完成したのは Loday [Lod04] らしい。

Permutohedron は, Milgram の仕事 [Mil66] に登場するように, 多重ループ空間と関係が深い。 Kadeishvili と Saneblidze [KS15] によると, ループ空間の chain complex のモデルを考える際には, permutohedron に基づいた permutohedral set を用いるとよいようである。(Saneblidze と Umble の [SU04])

その Sanbelidze と Umble の論文で与えられた permutohedron の diagonal を, 計算機で計算することを [Vej] で Vejdemo-Johansson が考えている。

面を定義する不等式をいくつか除いたものを, Pilaud [Pil17] は removahedron と呼んでいる。

• removahedron

一方で面を定義する超平面を平行移動させたものは, deformed permutothedron と呼ばれている。

• deformed permutohedron

例えば nestohedron や graph associahedron は deformed permutohedron になっている, らしい。Pilaud [Pil17] は, どの nestohedron が removahedron であるかという問題を考えている。

他にも, 一般化として Schulte ら5人組の [Ara+10] で定義された graphicahedron というものもある。

• graphicahedron

これは, graph から定義されるものであり, 直線状の graph の場合が, 古典的な permutohedron になるようである。

Tsukerman と Williams [TW15] は, Bruhat interval polytope という変種を調べている。Kodama と Williams の [KW15] の Appendix に登場する。これは, permutohedron の辺が対称群の weak Bruhat order の cover relation と1対1に対応することからの一般化である。Pairmutohedron や mutohedron などの名前が提案されている。 Willaimsは [Wil16] で bridge polytope という変種も定義している。

References

[AA]

Marcelo Aguiar and Federico Ardila. Hopf monoids and generalized permutahedra. arXiv: 1709.07504.

[Ara+10]

Gabriela Araujo-Pardo, Maria Del Rı́o-Francos, Mariana López-Dudet, Deborah Oliveros, and Egon Schulte. “The graphicahedron”. In: European J. Combin. 31.7 (2010), pp. 1868–1879. arXiv: 0910.3908. url: http://dx.doi.org/10.1016/j.ejc.2010.03.004.

[AS]

Federico Ardila and Mario Sanchez. Valuations and the Hopf Monoid of Generalized Permutahedra. arXiv: 2010.11178.

[BIP19]

Djordje Baralić, Jelena Ivanović, and Zoran Petrić. “A simple permutoassociahedron”. In: Discrete Math. 342.12 (2019), pp. 111591, 18. arXiv: 1708.02482. url: https://doi.org/10.1016/j.disc.2019.07.007.

[CL]

Federico Castillo and Fu Liu. The permuto-associahedron revisited. arXiv: 2109.08658.

[GR63]

G. Th. Guilbaud and P. Rosenstiehl. “Analyse algébrique d’un scrutin”. In: Mathématiques et Sciences humaines 4 (1963), pp. 9–33. url: http://www.numdam.org/item/MSH_1963__4__9_0/.

[Hoh12]

Christophe Hohlweg. “Permutahedra and associahedra: generalized associahedra from the geometry of finite reflection groups”. In: Associahedra, Tamari lattices and related structures. Vol. 299. Prog. Math. Phys. Birkhäuser/Springer, Basel, 2012, pp. 129–159. arXiv: 1112.3255. url: https://doi.org/10.1007/978-3-0348-0405-9_8.

[Iva]

Jelena Ivanovic. Geometrical Realisations of the Simple Permutoassociahedron by Minkowski sums. arXiv: 1904.06700.

[Kap93]

Mikhail M. Kapranov. “The permutoassociahedron, Mac Lane’s coherence theorem and asymptotic zones for the KZ equation”. In: J. Pure Appl. Algebra 85.2 (1993), pp. 119–142. url: http://dx.doi.org/10.1016/0022-4049(93)90049-Y.

[KS15]

Tornike Kadeishvili and Samson Saneblidze. “The twisted Cartesian model for the double path fibration”. In: Georgian Math. J. 22.4 (2015), pp. 489–508. arXiv: math / 0210224. url: https://doi.org/10.1515/gmj-2015-0040.

[KW15]

Yuji Kodama and Lauren Williams. “The full Kostant-Toda hierarchy on the positive flag variety”. In: Comm. Math. Phys. 335.1 (2015), pp. 247–283. arXiv: 1308 . 5011. url: https://doi.org/10.1007/s00220-014-2203-x.

[Lod04]

Jean-Louis Loday. “Realization of the Stasheff polytope”. In: Arch. Math. (Basel) 83.3 (2004), pp. 267–278. arXiv: math/0212126. url: http://dx.doi.org/10.1007/s00013-004-1026-y.

[Mil66]

R. James Milgram. “Iterated loop spaces”. In: Ann. of Math. (2) 84 (1966), pp. 386–403. url: http://dx.doi.org/10.2307/1970453.

[Oh13]

Suho Oh. “Generalized permutohedra, \(h\)-vectors of cotransversal matroids and pure O-sequences”. In: Electron. J. Combin. 20.3 (2013), Paper 14, 14. arXiv: 1005.5586.

[Pil17]

Vincent Pilaud. “Which nestohedra are removahedra?” In: Rev. Colombiana Mat. 51.1 (2017), pp. 21–42. arXiv: 1407.2464. url: https://doi.org/10.15446/recolma.v51n1.66833.

[Pos09]

Alexander Postnikov. “Permutohedra, associahedra, and beyond”. In: Int. Math. Res. Not. IMRN 6 (2009), pp. 1026–1106. arXiv: math/0507163. url: https://doi.org/10.1093/imrn/rnn153.

[PRW08]

Alex Postnikov, Victor Reiner, and Lauren Williams. “Faces of generalized permutohedra”. In: Doc. Math. 13 (2008), pp. 207–273. arXiv: math/0609184.

[RZ94]

Victor Reiner and Günter M. Ziegler. “Coxeter-associahedra”. In: Mathematika 41.2 (1994), pp. 364–393. url: http://dx.doi.org/10.1112/S0025579300007452.

[Sch11]

Pieter Hendrik Schoute. “Analytical treatment of the polytopes regularly derived from the regular polytopes”. In: Verhandelingen der Koninklijke Akademie van Wetenschappen Te Amsterdam 11.3 (1911), pp. 1–82. url: https://www.dwc.knaw.nl/toegangen/digital-library-knaw/?pagetype=publDetail&pId=PU00011495.

[SS93]

Steven Shnider and Shlomo Sternberg. Quantum groups. Graduate Texts in Mathematical Physics, II. From coalgebras to Drinfel\('\)d algebras, A guided tour. Cambridge, MA: International Press, 1993, pp. xxii+496. isbn: 1-57146-000-4.

[SU04]

Samson Saneblidze and Ronald Umble. “Diagonals on the permutahedra, multiplihedra and associahedra”. In: Homology Homotopy Appl. 6.1 (2004), pp. 363–411. arXiv: math/0209109. url: http://projecteuclid.org/euclid.hha/1139839559.

[TW15]

E. Tsukerman and L. Williams. “Bruhat interval polytopes”. In: Adv. Math. 285 (2015), pp. 766–810. arXiv: 1406 . 5202. url: https://doi.org/10.1016/j.aim.2015.07.030.

[Vej]

Mikael Vejdemo-Johansson. Enumerating the Saneblidze-Umble diagonal terms. arXiv: 0707.4399.

[Wil16]

Lauren K. Williams. “A positive Grassmannian analogue of the permutohedron”. In: Proc. Amer. Math. Soc. 144.6 (2016), pp. 2419–2436. arXiv: 1501.00714. url: https://doi.org/10.1090/proc/12923.

[Zie95]

Günter M. Ziegler. Lectures on polytopes. Vol. 152. Graduate Texts in Mathematics. Springer-Verlag, New York, 1995, pp. x+370. isbn: 0-387-94365-X. url: https://doi.org/10.1007/978-1-4613-8431-1.