papatagonian’s blog

hベクトルの対称性

以前、simple polytopeはグラフから組合せ構造が復元できるというKalaiの結果を紹介しました。そこで登場したgeneric directonによる頂点の順位付けに関する話です。

定理

$P \subset \mathbb{R}^d$ を $d$ -次元単純凸多面体とする。 $\ell \in (\mathbb{R}^d)^*$ をgenericな一次関数とし、 $P$ の頂点 $1,\ldots,n$ は、 $\ell (1) \lt \cdots \lt \ell (n)$ を満たすとする。 $P$ のグラフ $G(P)$ の各辺を $\ell$ の値が小さい方から大きい方へ向きづける。 $h_i$ を入次数 $i$ の頂点数とするとき、 $h_i=h_{d-i} (i=0,\ldots,d)$ が成り立つ。

証明

明らかに $h_0=h_d=1$ である。各 $i=1,\ldots,d$ について、 $P$ の $i$ -次元面の数を $f_i$ とする。

主張の有向グラフを各面に制限してもsinkはただ一つ。
simpleであることから、任意の頂点 $v \in V(P)$ について、 $v$ をsinkとしてもつ $i$ 次元面の数は、 $\binom{d_v}{i}$ 。ただし、 $d_v$ は頂点 $v$ の入次数。

よって $i$ 次元面とそのsinkのペアの数をダブルカウントすることにより、各 $i=0, \ldots, d$ について、 $f_i = \sum_{j=0}^{d} \binom{j}{i} h_j$ となる。ここで、 $j\lt i$ のとき $\binom{j}{i}=0$ なので、これは $\{f_i\}$ の値から $\{h_i\}$ の値が一意に決まることを言っている。

実はここまでの議論は、 $\ell$ の取り方によらないものになっている。したがって、 $\{h_i\}$ の値は $\ell$ の取り方によらない。特に $\ell$ の代わりに $-\ell$ をとることによって、定理が示される。

コメント

$\{h_i\}$ は $P$ の双対多面体の $h$ ベクトルとよばれるものに一致します。上の定理は多面体に関するDehn-Summervilleの定理の初等的な証明となっています。
単純多面体のgeneric directionによる番号づけは、 $P$ の双対の単体的多面体のshelling orderを与えます。