駆け足で読む『離散体積計算による組合せ数学入門』第3章 多面体の格子点を数える:Ehrhart理論

  • 任意の凸多面体は新たな頂点を加えずに三角形分割できる
    • 三角形分割とは、共通面のみで接する(重なる)ようなd-単体(これが三角形のようなもの)の集合に分けること。2次元での三角形分割の多次元一般化。
  • 尖状錐(pointed cone)
    • 尖状錐とは、ある点とそこからのベクトルである生成元の非負線形結合で定義できる多面体である。尖状錐では、「ある点」を含む超平面があって、尖状錐はこの超平面と「ある点」のみで重なる(片側にあルる)
    • 尖状錐が単体的であるとは、生成元が線形独立な場合
    • 例えば、多面体を1つ次元の高い空間に置き直せば、「錐」とすることができる
    • 尖状錐は単体的錐に三角形分割できる
  • 有理錐に対する整数点変換
    • 有理錐は、整数を成分とする生成元で表せる
    • 錐の中に、格子点を頂点とする「基本平行体(平行四辺形の多次元版)」を取ると、それに含まれる格子点の数は計算できて、それを錐の中に敷き詰めることで、錐の格子点数を計算する、という方法がある
  • 多面体の離散体積から連続体積へ
    • 多面体の離散体積は、多項式で表される
    • 連続体積は、その離散体積の多項式の項の1つに相当する