凸多面体についての教科書。
絵も多く、非常に分かりやすく書かれている。また、
新しい話題にも多数触れられており、各章末のnoteと併せて、
研究の最前線のワクワク感を感じることもできる。
随所に取り混ぜられているちょっとしたジョークも読んでいて
親しみが感じられて楽しい。
多面体関係の研究をしたい人だけでなく、多くの人に読んでもらいたい、
お勧めの本である。
1998年にsecond printingが出て、ページ数とreferenceが増えた。著者のページ
http://www.math.tu-berlin.de/~ziegler
から、訂正および最新情報のファイルが入手できる。
[Contents]
| 0. | Introduction and Examples | |
| 1. | Polytopes, Polyhedra, and Cones | |
| 2. | Faces of Polytopes | |
| 3. | Graphs of Polytopes | |
| 4. | Steinitz' Theorem for 3-Polytopes | |
| 5. | Schlegel Diagrams for 4-Polytopes | |
| 6. | Duality, Gale Diagrams, and Applications | |
| 7. | Fans, Arrangements, Zonotopes, and Tilings | |
| 8. | Shellability and the Upper Bound Theorem | |
| 9. | Fiber Polytopes, and Beyond |
本書の日本語訳は、シュプリンガー・フェアラーク東京から『凸多面体の数学』というタイトルで出ています。
これはグラフ理論に現れる離散的な概念を実数的なものに緩和する
とどうなるかを種々論じる、fractional graph theoryの入門書。
実数的に緩和するが、結局有理数に落ち着くことが示されるので、
「fractional」と呼ばれている。
Fractional graph theoryという、少し特殊な話が中心ではあるが、
同時に普通のグラフ理論やハイパーグラフ、マトロイドの話も
学ぶことができ、一石二鳥である。
グラフ理論などの離散数学の話題を勉強したいが、普通のグラフ
理論の本では飽きたらない、というような人にお勧め。
http://www.mts.jhu.edu/~fgt
に本の紹介と共にERRATAが載せられている。が、まだあまりないようである。
(今の所、Stahlの予想(3.2節の最後)が間違った形で掲載されているのが修正
されている。)
ただし、この本はindexの最後のページがどういうわけか抜け落ちており、この
抜け落ちてしまったページも置いてあるので、これは重要。
[Contents]
| 1. | General Theory: Hypergraphs |
| 2. | Fractional Matching |
| 3. | Fractional Coloring |
| 4. | Fractional Edge Coloring |
| 5. | Fractional Arboricity and Matroid Methods |
| 6. | Fractional Isomorphism |
| 7. | Fractional Odds and Ends |
| Appendix: Background |
組合せ論のあらゆる話題の解説記事をまとめたもの。
各章とも、その分野で最も有名と思われる研究者が執筆していて、
それぞれの分野の概要を知るのによい。
ただし、証明などは書かれていないことが多いので、詳しく知りたい
場合はさらにその分野の教科書なり論文なりに進む必要がある。
論文などで知らない概念が出てきたときなど、定義と周辺分野の
様子を簡単に把握したいときなどに重宝する。
ちなみに、34章のTopological Methodsがお気に入り。
[Contents]省略
「組合せ最適化」の教科書。著者はいずれもこの分野の有名人。
組合せ最適化とは、組合せ的な制約下で目的の量を最大化・最小化
するにはどうしたらよいか、というようなことを議論する分野で、
例えば、各辺に長さが与えられたグラフ上である頂点からある頂点
への最短のパスを探す、とかいうことが問題になる。この本では、
この手の組合せ最適化問題に対して答を与えるためのアルゴリズム
を紹介しつつ、その背後にある理論も合わせて紹介されている。
というか、アルゴリズムの背後にある理論こそが組合せ最適化の
主役なので、これは当然のことでもある。
実は、これを読んでいたときは、記述が分かりにくいとみんなで
文句を言っていたので、この本がお勧めの教科書かどうかは少し
微妙であるが、書いてあることは非常にすばらしい(のだと思う)。
とにかく、離散数学や計算の理論を学ぼうという人は、この本か
別の本かはともかく、組合せ最適化およびその思想を少しは
かじっておくことをお勧めする。
(代案は Korte & Vygen, `Combinatorial Optimization', Springer (Algorithms and Combinatorics 21), 2000 かもしれない。 )
[Contents]
| 1. | Problems and Algorithms |
| 2. | Optimal ATrees and Paths |
| 3. | Maximum Flow Problems |
| 4. | Minimum-Cost Flow Problems |
| 5. | Optimal Matchings |
| 6. | Integrality of Polyhedra |
| 7. | The Traveling Salesman Problem |
| 8. | Matroids |
| 9. | NP and NP-completeness |
| Appendix A. Linear Programming |
有向マトロイドとは、マトロイドに符号をつけたもので、 例えばマトロイドでサーキットとはある部分集合のことを指し、 これはこの部分集合に入っていたら1、 入っていなかったら0 という{0,1}ベクトルで記述できるが、 有向マトロイドではこれを{0,1,-1}ベクトルで記述し、各要素 に+か-の符号がついているものとして扱うものである。
「有向マトロイド」というのは、このような{0,1,-1}ベクトルの 集合で、ある公理系を満たすもののことをいう。
この有向マトロイドはマトロイドと同様にグラフのサーキットの 全体や木の全体などを記述するが、さらに、凸多面体、ゾノトープ、 超平面配置、グラスマン多様体なども記述する。
1-2章がイントロダクションで、有向マトロイドの登場するいろいろな 例があげられているが、この段階ではよく分からないこともあるので、 分からなくても気にせず先に進むとよい。また、3章は非常に多くの 等価な公理系が挙げられてその等価性が議論されているので、段々 飽きてくるが、これも気にせず先に進む(場合によっては飛ばす)と、 4章以降段々面白くなってくるはずである。
1999年に出た2nd ed.では、いくつか細かい間違いが直された他、
Appendixがついている。運悪く古い方を手にしてしまった場合は、
Gunter M. Ziegler, Oriented Matroids, Electronic Journal of Combinatorics, DS4 (1998)
(http://www.combinatorics.org/
の「Surveys」からたどる。)
が2nd ed.との差分的なものになっているので、これを入手するとよい。
[Contents]
| 1. | A First Orientation Session |
| 2. | A Second Orientation Session |
| 3. | Axiomatics |
| 4. | From Face Lattices to Topology |
| 5. | Topological Models for Oriented Matroids |
| 6. | Arrangements of Pseudolines |
| 7. | Constructions |
| 8. | Realizability |
| 9. | Convex Polytopes |
| 10. | Linear Programming |
| Appendix: Some Current Frontiers of Research |
初歩的なトポロジーの入門書。
二次元閉曲面の分類、基本群やホモロジー、結び目などの紹介の他、
最後の章で多様体の同相性判定問題が一般には計算不可能(4次元以上で)である
ことが解説されている。
(この計算不可能性は群のword problemを経由して示されているが、
Second Editionのprefaceによると、この方法は1980年頃にCohen-Aanderaaに
よって発見されたということで、
9章はSecond Editionで付け加えられたとのことである。)
[Contents]
| 0. | Introduction and foundations |
| 1. | Complex Analysis and Surface Topology |
| 2. | Graphs and Free Groups |
| 3. | Foundations for the Fundamental Group |
| 4. | Fundamental Groups of Complexes |
| 5. | Homology Theory and Abelianization |
| 6. | Curves on Surfaces |
| 7. | Knots and Braids |
| 8. | Three-Dimensional Manifolds |
| 9. | Unsolvable Problems |