\(\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] がある。
この 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 と呼んでいる。
一方で面を定義する超平面を平行移動させたものは, deformed permutothedron と呼ばれている。
例えば nestohedron や graph associahedron は deformed permutohedron になっている,
らしい。Pilaud [Pil17] は, どの nestohedron が removahedron であるかという問題を考えている。
他にも, 一般化として Schulte ら5人組の [Ara+10] で定義された 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.
|