離散幾何学講義

目次

• まえがき
• 日本語版まえがき
• 記法と用語
• 第1章 凸性の理論
  • 1.1 線形部分空間，アフィン部分空間，一般の位置
  • 1.2 凸集合，凸結合，分離定理
  • 1.3 Radonの補題とHellyの定理
  • 1.4 中心点定理とハム・サンドイッチ定理
• 第2章 格子とMinkowskiの定理
  • 2.1 Minkowskiの定理
  • 2.2 一般の格子
  • 2.3 数論での応用
• 第3章 凸独立部分集合
  • 3.1 Erdős-Szekeresの定理
  • 3.2 Horton集合
• 第4章 接続問題
  • 4.1 問題の定式化
  • 4.2 接続問題と単位距離の下界
  • 4.3 点-直線接続対と交差数
  • 4.4 相違距離と交差数
  • 4.5 点-直線接続対とカッティング
  • 4.6 カッティング補題の弱いバージョン
  • 4.7 カッティング補題：タイトな上界
• 第5章 凸多面体
  • 5.1 幾何的双対性
  • 5.2 H-多面体とV-多面体
  • 5.3 凸多面体の面
  • 5.4 面の数：巡回多面体
  • 5.5 上限定理
  • 5.6 Gale変換
  • 5.7 Voronoi図
• 第6章 アレンジメントにおける面の数
  • 6.1 超平面アレンジメント
  • 6.2 その他の幾何的対象のアレンジメント
  • 6.3 k以下レベルの頂点数
  • 6.4 ゾーン定理
  • 6.5 カッティング補題再訪
• 第7章 下側エンベロープ
  • 7.1 線分アレンジメントとDavenport-Schinzel列
  • 7.2 線分集合の下側エンベロープの超線形複雑さ
  • 7.3 Davenport-Schinzel列に戻って
  • 7.4 線分に対するタイトな上界に向けて
  • 7.5 高次元へ上がると：空間における三角形
  • 7.6 平面上の曲線
  • 7.7 代数曲面パッチ
• 第8章 凸集合の交わりパターン
  • 8.1 分数版Hellyの定理
  • 8.2 彩色版Carathéodoryの定理
  • 8.3 Tverbergの定理
• 第9章 幾何的選択定理
  • 9.1 第一選択補題
  • 9.2 第二選択補題
  • 9.3 順序タイプと同タイプ補題
  • 9.4 ハイパーグラフの正側性補題
  • 9.5 正比率選択補題
• 第10章 横断理論とε-ネット
  • 10.1 一般的な準備：横断とマッチング
  • 10.2 ε-ネットとVC次元
  • 10.3 VC次元の有界性と応用
  • 10.4 凸集合に対する弱ε-ネット
  • 10.5 Hadwiger-Debrunnerの(p,q)-問題
  • 10.6 超平面横断に対する(p,q)-定理
• 第11章 点配置におけるk-集合問題
  • 11.1 定義と最初の評価
  • 11.2 等分割辺の数が多い集合
  • 11.3 Lovászの補題と全ての次元に対する上界
  • 11.4 平面に対する上界の改善
• 第12章 高次元多面体の2つの応用
  • 12.1 弱理想グラフ予想
  • 12.2 Brunn-Minkowskiの不等式
  • 12.3 半順序集合のソート
• 第13章 高次元における体積
  • 13.1 体積，高次元のパラドックス，ネット
  • 13.2 体積近似の難しさ
  • 13.3 体積が大きい多面体の構成法
  • 13.4 楕円体による凸体の近似
• 第14章 測度集中と概球面切断
  • 14.1 球面上の測度集中
  • 14.2 等周不等式と測度集中
  • 14.3 Lipschitz関数の集中
  • 14.4 概球面切断：はじめの一歩
  • 14.5 中心対称多面体の面の数
  • 14.6 Dvoretzkyの定理
• 第15章 有限距離空間のノルム空間への埋め込み
  • 15.1 導入：近似埋め込み
  • 15.2 Johnson-Lindenstraussの平坦化補題
  • 15.3 数え上げによる下界
  • 15.4 Hamming立方体に対する下界
  • 15.5 エクスパンダによるタイトな下界
  • 15.6 Fourier変換によるタイトな下界
  • 15.7 ℓ_∞に対する上界
  • 15.8 Euclid埋め込みに対する上界
  • 15.9 近似埋め込みの進展：2002年〜2005年
• まとめ (各章の要点)
• 演習問題のヒント
• 参考文献
• 訳者あとがき
• 索引

各章は2002年に出版された原著に対してところどころ改訂を加えたものに基いています。