凸多面体の単体分割

Ziegler の [Zie99] によると, 凸多面体の組み合せ論では, 凸多面体の単体分割は重要な研究分野の一つのようである。 単に 組み合せ論の問題として面白いだけでなく, 様々な応用がある。これについては, De Loera と Rambau と Santos の本 [DRS10] をみるとよい。

この本で扱われている問題は次のようなものである。

1. 与えられた凸多面体の単体分割の数を数える
2. ある性質を持つ単体分割が存在するかどうか
3. そのような単体分割の中でoptimalなものを見つける
4. 与えられた凸多面体の単体分割全体の集合の代数的, あるいはトポロジカルな性質を調べる

第6章では, いくつかの具体例について解説されているが, そこに登場するのは次のものである。

• cyclic polytope
• 2つの単体の直積
• 立方体やそのsubpolytope

例えば, Santos の [San13] では, 単体の直積 \(\Delta ^k\times \Delta ^{\ell }\) の単体分割については, Fardila と Ceballos の [AC13], Ardila と Billey の [AB07], Santos の [San05b] などが挙げられている。Ardila らの論文によると, 単体の直積の単体分割は, tropical hyperplane arrangement と関係があるようである。

Santos の [San05b] では, polyhedral Cayley trick というものが使われている。Polyhedral Cayley trick は, Sturmfels [Stu94] や Huber, Rambau, Santos [HRS00] などによるものらしい。

Cyclic polytope の単体分割は, Oppermann と Thomas [OT12] により表現論との関係が発見されたが, 単体の直積の単体分割も表現論と関係があるらしい。 \(\Delta ^{n}\times \Delta ^{1}\) の場合を Iyama と Williams [IW] が調べている。

多面体の単体分割を考えるときは, 多面体をその頂点の convex hull と考え, 頂点集合に対する操作と考える。 このような Euclid 空間の有限個の点の集合を point configuration というが, より一般に point configuration の単体分割の問題が考えられる。 前述の De Loera らの本 [DRS10] の主題は, point configuration の単体分割である。

• point configuration
• triangulation of point configuration

Lattice polytope の場合は unimodular simplex による unimodular triangulation が重要である。

• unimodular triangulation

Point configuration や多面体の不変量として, 単体分割全体から成るのグラフがある。 簡単な説明が Santos の [San05a] にある。

• point set の単体分割全体を頂点としたグラフ

ある多面体 (point configuration) の単体分割を考えるとき, このグラフの連結性がまず問題となる。単体分割のグラフが連結でない例があるか, という問題に解答を与えたのが, Santos の [San00] である。 その例は\(324\)個の点から成るものであるが, ずっと小さな例が Santos の [San05a] で発見された。

この Santos の論文のタイトルにある toric Hilbert scheme は, Peeva と Stillman [PS02] により定義されたもので, toric ideal に関係したものである。古典的な Hilbert scheme とはちょっと違って, その連結性もよく分っていない。Maclagan と Thomas の [MT02] などを見るとよい。

凸多角形の三角形分割も色々面白いことがあるようである。 Adin と Roichman の [AFR10] では, 少なくとも一つの辺が境界にある三角形分割を triangle-free triangulation と呼び, graphic hyperplane arrangement との関係が調べられている。

• triangle-free triangulation

References

[AB07]

Federico Ardila and Sara Billey. “Flag arrangements and triangulations of products of simplices”. In: Adv. Math. 214.2 (2007), pp. 495–524. arXiv: math/0605598. url: https://doi.org/10.1016/j.aim.2007.02.014.

[AC13]

Federico Ardila and Cesar Ceballos. “Acyclic systems of permutations and fine mixed subdivisions of simplices”. In: Discrete Comput. Geom. 49.3 (2013), pp. 485–510. arXiv: 1111 . 2966. url: https://doi.org/10.1007/s00454-013-9485-1.

[AFR10]

Ron M. Adin, Marcelo Firer, and Yuval Roichman. “Triangle-free triangulations”. In: Adv. in Appl. Math. 45.1 (2010), pp. 77–95. arXiv: 1009.2628. url: http://dx.doi.org/10.1016/j.aam.2009.11.001.

[DRS10]

Jesús A. De Loera, Jörg Rambau, and Francisco Santos. Triangulations. Vol. 25. Algorithms and Computation in Mathematics. Structures for algorithms and applications. Berlin: Springer-Verlag, 2010, pp. xiv+535. isbn: 978-3-642-12970-4. url: http://dx.doi.org/10.1007/978-3-642-12971-1.

[HRS00]

Birkett Huber, Jörg Rambau, and Francisco Santos. “The Cayley trick, lifting subdivisions and the Bohne-Dress theorem on zonotopal tilings”. In: J. Eur. Math. Soc. (JEMS) 2.2 (2000), pp. 179–198. url: http://dx.doi.org/10.1007/s100970050003.

[IW]

Osamu Iyama and Nicholas J. Williams. Triangulations of prisms and preprojective algebras of type \(A\). arXiv: 2208.12957.

[MT02]

D. Maclagan and R. R. Thomas. “Combinatorics of the toric Hilbert scheme”. In: Discrete Comput. Geom. 27.2 (2002), pp. 249–272.

[OT12]

Steffen Oppermann and Hugh Thomas. “Higher-dimensional cluster combinatorics and representation theory”. In: J. Eur. Math. Soc. (JEMS) 14.6 (2012), pp. 1679–1737. arXiv: 1001 . 5437. url: https://doi.org/10.4171/JEMS/345.

[PS02]

Irena Peeva and Mike Stillman. “Toric Hilbert schemes”. In: Duke Math. J. 111.3 (2002), pp. 419–449. url: http://dx.doi.org/10.1215/S0012-7094-02-11132-6.

[San00]

Francisco Santos. “A point set whose space of triangulations is disconnected”. In: J. Amer. Math. Soc. 13.3 (2000), 611–637 (electronic). url: http://dx.doi.org/10.1090/S0894-0347-00-00330-1.

[San05a]

Francisco Santos. “Non-connected toric Hilbert schemes”. In: Math. Ann. 332.3 (2005), pp. 645–665. url: http://dx.doi.org/10.1007/s00208-005-0643-5.

[San05b]

Francisco Santos. “The Cayley trick and triangulations of products of simplices”. In: Integer points in polyhedra—geometry, number theory, algebra, optimization. Vol. 374. Contemp. Math. Amer. Math. Soc., Providence, RI, 2005, pp. 151–177. arXiv: math/0312069. url: https://doi.org/10.1090/conm/374/06904.

[San13]

Francisco Santos. “Some acyclic systems of permutations are not realizable by triangulations of a product of simplices”. In: Algebraic and combinatorial aspects of tropical geometry. Vol. 589. Contemp. Math. Amer. Math. Soc., Providence, RI, 2013, pp. 317–328. arXiv: 1201.0529. url: https://doi.org/10.1090/conm/589/11749.

[Stu94]

Bernd Sturmfels. “On the Newton polytope of the resultant”. In: J. Algebraic Combin. 3.2 (1994), pp. 207–236. url: http://dx.doi.org/10.1023/A:1022497624378.

[Zie99]

Günter M. Ziegler. “Recent progress on polytopes”. In: Advances in discrete and computational geometry (South Hadley, MA, 1996). Vol. 223. Contemp. Math. Providence, RI: Amer. Math. Soc., 1999, pp. 395–406.