凸多面体の基礎

組み合せ論的視点からの凸多面体の教科書としては, 例えば Grünbaum の [Grü03] や Ziegler の [Zie95] といった本がある。Ziegler の本は, 多面体の基礎, 特に多面体の組み合せ論を勉強するための教科書として, よく挙げられている。 Ziegler は, 他にも [Zie07] という解説を書いている。 これは最近の話題, 特に \(f\)-vector と extremal construction についての解説であるが。

その Ziegler の [Zie07] の Appendix で紹介されているものに, polymake という software がある。UNIX 系の OS でないと動かないようであるが。解説としては, [GJ] がある。他にも, SageMath でも, 多面体を扱うことができる。

多面体といって, ほとんどの人が思い浮かべるのは, 正四面体や立方体などの正多面体だと思うが, 他に実に様々な多面体がとても幅広い分野で登場する。 目にしたものを, 次にまとめた。

• 多面体の例

凸多面体は, その名前が示すように凸集合であるが, Euclide 空間の部分空間に限らない凸集合の定義として monad を用いた Fritz の [Fri] がある。

凸多面体には, 頂点の凸包として定義するものと, 超平面により切取られた有界領域として定義するものという二つの流儀がある。 Ziegler は, 前者を \(\mathcal{V}\)-polytope, 後者を \(\mathcal{H}\)-polytope と言っている。 Ziegler によると, 凸多面体の基本定理はこの二つが同値であることである。

• \(\mathcal{V}\)-polytope の定義
• \(\mathcal{H}\)-polytope の定義
• \(\mathcal{V}\)-polytope は \(\mathcal{H}\)-polytope として表わすことができ, 逆に \(\mathcal{H}\)-polytope は \(\mathcal{V}\)-polytope として表わすことができる。

ただし, この二つが同値であるとは言っても, 具体的な多面体について, その変換を行なうのは容易ではない。この変換の問題は, convex hull problem と呼ばれている。Joswig と Ziegler の [JZ04] の Introduction を読むとよい。二つが同値であることの証明自体も面倒である。Ziegler の本には詳しい証明があるし, Gallier の [Gal] にも証明がある。

\(\mathcal{H}\)-polytope の定義を見ると, 有界性は本質的ではないように思える。\(\mathcal{H}\)-polytope の定義で有界性を仮定しないものを \(\mathcal{H}\)-polyhedron と言うが, 対応する \(\mathcal{V}\)-polyhedron を定義するためには Minkowski sum という操作が必要になる。

• Minkowski sum
• \(\mathcal{V}\)-cone と \(\mathcal{H}\)-cone

多面体の組み合せ論的構造を表わすデータとして face lattice は基本である。 また, 頂点, 辺, 面等の数を順に並べた \(f\)-vector も重要なデータである。

• face lattice
• \(f\)-vector
• \(h\)-vector

多面体の Minkowski sum を取ったときの \(f\)-vector の評価については, Fukuda と Weibel の [FW] がある。頂点の数を決めたときに, その面数, つまり \(f\)-vector を評価するという問題もある。これについては, McMullen [McM70] と Varnette [Bar73] の結果がある。

多面体を \(\mathcal{V}\)-polytope として考えたときに, 頂点の他にできるだけ少ないデータで多面体が表わせると便利である。 最も単純なのは, どの二つの頂点が辺で結ばれているかというデータである。 これを多面体のグラフという。

• 多面体のグラフ

多角形の場合には, 内接円や外接円の存在の問題が考えられるが, それを凸多面体に一般化したのが scribability の問題である。 Chen と Padrol の [CP] によると, 19世紀に Steiner により3次元凸多面体の外接球, 内接球の存在の問題が提案されている, らしい。 3次元の場合, 外接球は全ての2次元面に接する球面, 内接球は全ての0次元面に接する球のことなので, 一般の次元では, 全ての \(k\)次元面に接する球の存在について議論することもできる。Schulte の [Sch87] が参照されている。Chen と Padrol は \((i,j)\)-scribable polytope の概念を導入している。

• \(k\)-scribable polytope
• weakly \(k\)-scribable polytope
• \((i,j)\)-scribable polytope

具体的に多面体を構成する際には, Billera と Sturmfels [BS92; BS94] により導入された fiber polytope は有用である。その起源となった Gel\('\)fand-Kapranov-Zelevinsky の secondary polytope [GZK89; GZK90] も重要である。

• fiber polytope
• fiber polytopeのmonotone path polytope
• secondary polytope

Fiber polytope という名前から, fibration を連想するが, Ziegler の本の最後には, fiber polytope を “fibration” とみなせるような convex polytope の category を構成するという問題がある。 これに関連して, Bogart と Contois と Gubeladze が [BCG13] で internal Hom を定義して調べている。その left adjoint, つまり tensor product も存在し, closed symmetric monoidal category になるようである。 Gubeladze と Love の[GL] も見るとよい。

• Hom-polytope
• tensor product polytope
• category of convex polytopes

更に polyhedral ではない convex set に拡張したものとして, Velasco の [Vel] がある。

多面体の集まりを扱う方法としては, category にすること以外に, 次のような方法がある。

• scissors congruence
• McMullen の polytope algebra [McM89]
• Cha, Friedl, Funke の Minkowski sum による Grothendieck group [CFF17]

Fiber polytope の monotone path polytope の例としては, permutohedron がある。これは \(\pi (x_1,\ldots ,x_n) = \sum _i x_i\) で与えられる fiber polytope \[ \pi : I^n \longrightarrow [0,n] \] の monotone path polytope である。これは zonotope になっている。

• zonotope
• zonotope に associate した hyperplane arrangement

Permutahedron に associate した hyperplane arrangement は, braid arrangement である。Braid arragement の deformation で得られる permutahedron の一般化について, [Ath99] で調べられている。 Zonotope に関連したことについては, Holz と Ron の [HR11] で zonotopal algebra の理論として調べられている。Xu との [HRX12] もある。

いわゆる双対多面体は, Ziegler の本では polar と呼ばれている。 関連した構成として, Wythoff construction がある。

• convex polytope の polar
• Wythoff construction

他に凸多面体に対する操作として次のようなものがある。

• wedge construction と wedge product (Rörig とZiegler の [RZ])

凸多面体の deformation が Castillo と Liu の [CL] で考えられている。

References

[Ath99]

C. A. Athanasiadis. “Piles of cubes, monotone path polytopes, and hyperplane arrangements”. In: Discrete Comput. Geom. 21.1 (1999), pp. 117–130. arXiv: math/9701207. url: http://dx.doi.org/10.1007/PL00009404.

[Bar73]

David Barnette. “A proof of the lower bound conjecture for convex polytopes”. In: Pacific J. Math. 46 (1973), pp. 349–354.

[BCG13]

Tristram Bogart, Mark Contois, and Joseph Gubeladze. “Hom-polytopes”. In: Math. Z. 273.3-4 (2013), pp. 1267–1296. arXiv: 1111.3880. url: https://doi.org/10.1007/s00209-012-1053-5.

[BS92]

Louis J. Billera and Bernd Sturmfels. “Fiber polytopes”. In: Ann. of Math. (2) 135.3 (1992), pp. 527–549. url: http://dx.doi.org/10.2307/2946575.

[BS94]

Louis J. Billera and Bernd Sturmfels. “Iterated fiber polytopes”. In: Mathematika 41.2 (1994), pp. 348–363. url: http://dx.doi.org/10.1112/S0025579300007440.

[CFF17]

Jae Choon Cha, Stefan Friedl, and Florian Funke. “The Grothendieck group of polytopes and norms”. In: Münster J. Math. 10.1 (2017), pp. 75–81. arXiv: 1512.06699. url: https://doi.org/10.17879/33249451813.

[CL]

Federico Castillo and Fu Liu. Deformation Cones of Nested Braid Fans. arXiv: 1710.01899.

[CP]

Hao Chen and Arnau Padrol. Scribability problems for polytopes. arXiv: 1508.03537.

[Fri]

Tobias Fritz. Convex Spaces I: Definition and Examples. arXiv: 0903.5522.

[FW]

Komei Fukuda and Christophe Weibel. On \(f\)-vectors of Minkowski additions of convex polytopes. arXiv: math/0510470.

[Gal]

Jean Gallier. Notes on Convex Sets, Polytopes, Polyhedra, Combinatorial Topology, Voronoi Diagrams and Delaunay Triangulations. arXiv: 0805.0292.

[GJ]

Ewgenij Gawrilow and Michael Joswig. Geometric Reasoning with polymake. arXiv: math/0507273.

[GL]

Joseph Gubeladze and Jack Love. Vertex maps between simplices, cubes, and crosspolytopes. arXiv: 1304.3775.

[Grü03]

Branko Grünbaum. Convex polytopes. Second. Vol. 221. Graduate Texts in Mathematics. Prepared and with a preface by Volker Kaibel, Victor Klee and Günter M. Ziegler. Springer-Verlag, New York, 2003, pp. xvi+468. isbn: 0-387-00424-6; 0-387-40409-0. url: https://doi.org/10.1007/978-1-4613-0019-9.

[GZK89]

I. M. Gel\('\)fand, A. V. Zelevinskiı̆, and M. M. Kapranov. “Newton polyhedra of principal \(A\)-determinants”. In: Dokl. Akad. Nauk SSSR 308.1 (1989), pp. 20–23.

[GZK90]

I. M. Gel\('\)fand, A. V. Zelevinskiı̆, and M. M. Kapranov. “Discriminants of polynomials in several variables and triangulations of Newton polyhedra”. In: Algebra i Analiz 2.3 (1990), pp. 1–62.

[HR11]

Olga Holtz and Amos Ron. “Zonotopal algebra”. In: Adv. Math. 227.2 (2011), pp. 847–894. arXiv: 0708.2632. url: https://doi.org/10.1016/j.aim.2011.02.012.

[HRX12]

Olga Holtz, Amos Ron, and Zhiqiang Xu. “Hierarchical zonotopal spaces”. In: Trans. Amer. Math. Soc. 364.2 (2012), pp. 745–766. arXiv: 0910.5543. url: https://doi.org/10.1090/S0002-9947-2011-05329-8.

[JZ04]

Michael Joswig and Günter M. Ziegler. “Convex hulls, oracles, and homology”. In: J. Symbolic Comput. 38.4 (2004), pp. 1247–1259. arXiv: math/0301100. url: http://dx.doi.org/10.1016/j.jsc.2003.08.006.

[McM70]

P. McMullen. “The maximum numbers of faces of a convex polytope”. In: Mathematika 17 (1970), pp. 179–184. url: https://doi.org/10.1112/S0025579300002850.

[McM89]

Peter McMullen. “The polytope algebra”. In: Adv. Math. 78.1 (1989), pp. 76–130. url: https://doi.org/10.1016/0001-8708(89)90029-7.

[RZ]

Thilo Rörig and Günter M. Ziegler. Polyhedral Surfaces in Wedge Products. arXiv: 0908.3159.

[Sch87]

E. Schulte. “Analogues of Steinitz’s theorem about noninscribable polytopes”. In: Intuitive geometry (Siófok, 1985). Vol. 48. Colloq. Math. Soc. János Bolyai. North-Holland, Amsterdam, 1987, pp. 503–516.

[Vel]

Mauricio Velasco. Linearization functors on real convex sets. arXiv: 1203.0946.

[Zie07]

Günter M. Ziegler. “Convex polytopes: extremal constructions and \(f\)-vector shapes”. In: Geometric combinatorics. Vol. 13. IAS/Park City Math. Ser. Providence, RI: Amer. Math. Soc., 2007, pp. 617–691. arXiv: math/0411400.

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