多面体的組み合わせ論（polyhedral combinatorics）の話題をいくつか．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

［１］置換多面体

　置換多面体は順列多面体（permutahedron）とも呼ばれる．３次元置換多面体は４文字あるいはベクトル（１，２，３，４）の座標の置換として可能な２４個のベクトルの凸包とみなすことができる．この多面体の辺が結ぶ２点は互換による入れ替わりだけの違いしかない．

　より詳細に調べると，置換多面体の構造と置換の性質の間の関係が他にも見つかっていく．

−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−

［２］巡回多面体

　ｆ0＝ｎとする．次元がｄ＝２のとき，多角形はｆ0＝ｆ1＝ｎ，ｆ2＝１である．ｄ＝３のとき，

　　ｆ1≦３ｎ−６，ｆ2≦２ｎ−４

等号が成り立つのは単体的多面体（すべての面が三角形）のときに限られる．

　ｄ＝２，３では面の数はｎに対して線形であったが，ｄ＝４ですべての頂点が変で結ばれている単体を考えると，辺の数は（ｎ，２）となって，多項式的である．ｄとｎが与えられたとき，巡回多面体と呼ばれる多面体が面数最大のなることが知られている．ファセット数の最大値のオーダーはｎ^[d/2]である．

−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−

［３］整数多面体

　整数多面体（integral polytope）あるいは格子多面体（lattice polytope）とはすべての頂点がＺ^nにあるような多面体．

−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−

［４］巡回セールスマン多面体

　置換行列が完全２部グラフＫn,nと対応するのに対して，巡回セールスマン多面体は完全グラフＫnに対応している．

　この多面体は（ｎ−１）！／２個の頂点をもつnＣ2−ｎ＝ｎ（ｎ−３）／２次元の多面体である．

　ところで，ｎ次元正単体は（ｎ＋１）個の点からなる完全グラフとみなすことができ，ｋ次元胞の数はｆk＝（ｎ＋１，ｋ＋１）である．完全グラフＫnは正ｎ角形にすべての対角線を引くことと同じであって，ｎ個の点からなり，ｋ次元胞の数はｆk＝（ｎ，ｋ＋１）である．

　したがって，巡回セールスマン多面体はｎ−１次元単体とは明らかに異なるものである．巡回セールスマン多面体（ＴＳＰ多面体）とは，完全グラフＫnのことではなく，ｎ点の凸包のことであって，ミンコフスキーの定理がいっていることは，ＴＳＰが線形計画法として正確にモデル化できるという事実にほかならない．そして，ＴＳＰ多面体のファセットは半空間を表す不等式によって面取りされるのである．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝