凸多面体の組み合せ論

多面体の組み合せ論の基礎については, 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 である。

凸多面体の組み合せ論の応用としてトーラスの作用を持つ多様体の研究は有名である。

• toric variety
• トーラスの作用を持つ多様体

ホモトピー論との関係では, permutohedron などの, operad と関係の深い多面体の族がある。

• 多面体と operad

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

• Mirković-Vilonen polytope

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

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

• 多面体のrealization space の universality
• 多面体の triangulation
• \(0/1\)-polytope
• neighborly polytope
• 多面体上の monotone path

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

• 多面体のグラフ
• Hirsch conjecture

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

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

• \(f\)-vector
• 多面体に含まれる lattice point の数

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

• 凸多面体の体積
• scissors congruence

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

• Stanley-Reisner 環

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

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

• 凸多面体の例

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.

[BV12]

Nicole Berline and Michèle Vergne. “Analytic continuation of a parametric polytope and wall-crossing”. In: Configuration spaces. Vol. 14. CRM Series. Ed. Norm., Pisa, 2012, pp. 111–172. arXiv: 1104.1885. url: https://doi.org/10.1007/978-88-7642-431-1_6.

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

[KS10]

Edward D. Kim and Francisco Santos. “An update on the Hirsch conjecture”. In: Jahresber. Dtsch. Math.-Ver. 112.2 (2010), pp. 73–98. arXiv: 0907.1186. url: https://doi.org/10.1365/s13291-010-0001-8.

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

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

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