凸多面体の組み合せ論

多面体組み合せ論につ の基礎については, Grünbaum の [Grü03] か Ziegler の [Zie95] を参照するのがよいだろう。Grünbaum の本は, 1967年に出たものであるが, 2002年に第二版がSpringer GTM (Graduate Texts in Mathematics) のシリーズから出ている。Zieglerの本もGTMから出ていて演 習問題が豊富にある。ただし, Ziegler の本は, 最初に Fourier-Motzkin elimination にページが割かれていて, 最初から順番に読んでいくと大変である。 他に, より基本的な内容に限定されるが, GTMにはBrøndstedの [Brø83]という本もある。

また combinatorial optimization における文献リストとして [DMM97] があるが, その中の polyhedral combinatorics についての章は, ここからdownloadできる。

最近 (?) の話題については, Ziegler による survey [Zie99] を見ると よい。7つの“challenge”が挙げてある。また, 文献としてEwaldの [Ewa96]とRichter-Gebertの[Ric96]が挙げてある。 Ewaldの本は, 代数幾何学との関連, つまり toric varietyと凸多面体との関連を解説したものである。 Part 1で凸多面体の組み合せ論について述べている。Richter-Gebertの本は realization spaceについてのmonographであ る。

凸多面体の組み合せ論の応用としてトーリック多様体の研究は有名である。 McDuffとTolmanは[MT10]で, toric symplectic manifoldを調べるた めに, simple polytopeのmass linear functionというものを考えている。

表現論には, Mirković-Vilonen polytopeという多面体が登場する。

有限群の表現に対してBirkoff polytopeの一般化になっている多面体の構成がある。Collins と Perkinson の [CP] など。 有限群の コホモロジーの計算にも使えるようである。Ellisらの [EHS06] である。

Zieglerの視点からは以下の問題が重要らしい:

多面体上のpathを考えるということは, その多面体の\(1\)-skeleton, つまり 多面体のグラフを考えるということである。 それに関してはHirsch cojectureという予想がある。KimとSantos [KS]によるsurveyがある。そのSantosは[San12]で counter exampleをannounceしている。

多面体のグラフは, \(3\)次元の凸多面体を調べるときに有効であるが, \(4\)次元 の凸多面体を調べる方法はまだ確立していないようである。Eppsteinと Kuperberg と Ziegler の [EKZ03] を見るとよい。 彼等は\(4\)次元凸多面体に対し, fatness という不変量を定義してその boundedness について調べている。

組み合せ論的には, 数 を数えるのが基本である。例えば, ある多面体 の内部に含まれるlattice pointの数とか。

関連した問題として, 多面体の体積の計算もある。[Xu11]の Introductionに挙げられている文献をみるとよい。BerlineとVergneの [BV]で定義されている, 凸多面体のcharacteristic functionの analytic continuationもlattice pointに関係がある。

  • 凸多面体の体積

多面体の単体分割も, 見掛けよりもずっと重要な 問題である。Santosは[San05b]などで単体の直積 \(\Delta ^k\times \Delta ^{\ell }\)の単体分割について考えている。そこでは polyhedral Cayley trickというものが使われている。Polyhedral Cayley trickは, Sturmfels, Huber, Rambau, Santosなど [Stu94; HRS00]によるものらしい。

多面体の単体分割を考えるときは, 多面体をその頂点のconvex hullと考え, 頂 点集合(point set)に対する操作と考える。すると, 問題は“point set”の単 体分割の問題となる。そして, 多面体 (point set) の不変量として, 単体分割 のグラフが得られる。簡単な説明がSantosの[San05a]にある。

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

凸多面体より一般的な有限単体的複体に対し て, Stanley-Reisner環という環が定義される。

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

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

BuchstaberとErokhovets [BEb; BEa]は全ての convex polytopeの集合から生成される 自由アーベル群からできるHopf algebraを考えて いる。

一般論だけでなく, 具体的な多面体の組み合せ論的構造を詳しく調べることも, もちろん重要である。

以上は, Euclid空間内の多面体であるが, 凸多面体の概念は様々な形に一般化 されている。

References

[BEa]

Victor M. Buchstaber and Nickolai Erokhovets. Polytopes, Hopf algebras and Quasi-symmetric functions. arXiv: 1011.1536.

[BEb]

Victor M. Buchstaber and Nickolai Erokhovets. Ring of Polytopes, Quasi-symmetric functions and Fibonacci numbers. arXiv: 1002.0810.

[Brø83]

Arne Brøndsted. An introduction to convex polytopes. Vol. 90. Graduate Texts in Mathematics. New York: Springer-Verlag, 1983, pp. viii+160. isbn: 0-387-90722-X.

[BV]

Nicole Berline and Michèle Vergne. Analytic continuation of a parametric polytope and wall-crossing. arXiv: 1104.1885.

[CP]

John Collins and David Perkinson. Frobenius polytopes. arXiv: 1102.0988.

[DMM97]

Mauro Dell’Amico, Francesco Maffioli, and Silvano Martello, eds. Annotated bibliographies in combinatorial optimization. Wiley-Interscience Series in Discrete Mathematics and Optimization. A Wiley-Interscience Publication. Chichester: John Wiley & Sons Ltd., 1997, pp. xiv+495. isbn: 0-471-96574-X.

[EHS06]

Graham Ellis, James Harris, and Emil Sköldberg. “Polytopal resolutions for finite groups”. In: J. Reine Angew. Math. 598 (2006), pp. 131–137. url: http://dx.doi.org/10.1515/CRELLE.2006.071.

[EKZ03]

David Eppstein, Greg Kuperberg, and Günter M. Ziegler. “Fat 4-polytopes and fatter 3-spheres”. In: Discrete geometry. Vol. 253. Monogr. Textbooks Pure Appl. Math. New York: Dekker, 2003, pp. 239–265. arXiv: math/0204007.

[Ewa96]

Günter Ewald. Combinatorial convexity and algebraic geometry. Vol. 168. Graduate Texts in Mathematics. New York: Springer-Verlag, 1996, pp. xiv+372. isbn: 0-387-94755-8.

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

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

[KS]

Edward D. Kim and Francisco Santos. An update on the Hirsch conjecture. arXiv: 0907.1186.

[MT02]

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

[MT10]

Dusa McDuff and Susan Tolman. “Polytopes with mass linear functions. I”. In: Int. Math. Res. Not. IMRN 8 (2010), pp. 1506–1574. arXiv: 0807.0900.

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

[Ric96]

Jürgen Richter-Gebert. Realization spaces of polytopes. Vol. 1643. Lecture Notes in Mathematics. Berlin: Springer-Verlag, 1996, pp. xii+187. isbn: 3-540-62084-2.

[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. url: http://dx.doi.org/10.1090/conm/374/06904.

[San12]

Francisco Santos. “A counterexample to the Hirsch conjecture”. In: Ann. of Math. (2) 176.1 (2012), pp. 383–412. arXiv: 1006.2814. url: http://dx.doi.org/10.4007/annals.2012.176.1.7.

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

[Xu11]

Zhiqiang Xu. “Multivariate splines and polytopes”. In: J. Approx. Theory 163.3 (2011), pp. 377–387. arXiv: 0806.1127. url: http://dx.doi.org/10.1016/j.jat.2010.10.005.

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

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