simple polytopeの組合せ構造の復元

多面体の組合せ論にずっとうっすら興味を持っていたのですが、なかなか重い腰が上がらず何も進んでいませんでした。今週思い立ってある論文を読もうとしましたが、読み始めたのが平日でその日は読みきれず、日を跨いだらNotationを忘れてしまい、結局絶賛放置中です。仕方ないので別のものに手を出すも、そちらも議論に振り落とされてしまい、もう自分には論文読めないのかと思っていた矢先に、めちゃくちゃ短いKalaiの論文が読めたのでそれの紹介です。

$P$ を $d$ 次元凸多面体とする． $G(P)=(V(P),E(P))$ を $P$ の $1$ -skeltonのなすグラフとする．

問

$G(P)$ から元の $P$ の組合せ構造を復元できるか（すなわち $P$ の面を全て列挙できるか）？

答えは実は一般にはNoである（後述するかも？）．Kalaiは以下の論文で $P$ がsimple（すなわち $G(P)$ が $d$ -正則）なときにYesであることを示した．

https://www.sciencedirect.com/science/article/pii/0097316588900647

これを紹介する．そもそもの発想と，途中でMorse関数のようなものを考えることが面白い．

証明の中身

まず，simple polytopeに関していくつか基本的な注意をしておく．

$P$ がsimpleなとき， $P$ の任意の面もsimpleである．実際 $P$ のfacetを考えると，少なくとも一本以上の辺がその支持超平面上にはなく， $d-1$ 次元多面体の頂点の次数は $d-1$ 以上であるためfacetについては成り立つ．これを繰り返し使うことで任意の次元の面についても言える．
またsimple polytopeのある頂点を $v$ ， $v$ に接続する辺全体の集合を $A$ とする．任意の部分集合 $B \subseteq A$ について， $v$ を含みかつ $A$ との交わりがちょうど $B$ であるような面がちょうど一つ存在する．存在については $v$ 周りの各超平面は $A$ のうちある辺だけを含まないものとなっているので， $B$ に対応する超平面の交わりを取ると言える．一意性については，存在するのであれば上記のことから次元は $\text{deg} v= |B|$ と等しいのでそれから従う．

$G(P)$ の辺の向きづけ $O$ で，有向サイクルを含まないようなもの(acyclic orientation)を考える．acyclic orientation $O$ がgoodとは， $P$ の任意の面 $F$ について， $O$ を誘導部分グラフ $G[F]$ に制限したものにsink（出次数 $0$ の頂点）が一つしか存在しないこととする．genericな方向の一次関数を考えることで，good acyclic orientationは常に存在することに注意しておく．

まずは与えられたacyclic orientationがgoodかどうかを， $G(P)$ のみから判定する方法を述べる．

acyclic orientation $O$ について， $h_k$ を入次数 $k$ の頂点数とし， $f_O := \sum_{k=0}^{k=d} 2^k h_k$ とする． $f_O$ は考える理由は次である．

$P$ の空集合を除く全ての次元の面の数の総和を $f$ とする．acyclic orientation $O$ を固定する．面 $F$ と，向きづけ $O$ を $F$ に制限した際のsink $v \in F$ の組 $(F,v)$ の総数を数えたいとする． $v$ の入次数が $k$ だとすると，注意の通り $v$ に入ってくる辺の任意の部分集合に対応する $2^k$ 個の面がとってこれる．よってそのような組 $(F,v)$ の総数はちょうど $f_O$ に等しい．どの面にもsinkは存在するのでこれは $f$ 以上．一方定義より， $O$ がgoodなら $f=f_O$ が成立する．

したがって，全てのacyclic orientationを考え， $f_O$ の最小値に一致するかどうかでgoodかどうかを判定できる．これが重要である．

よって次を示せば十分．

主張

$A \subset V(P)$ が $k$ -次元面をなすことは，誘導部分グラフ $G[A]$ が連結な $k$ -正則グラフで，かつあるgood acyclic orientation（から誘導される半順序）のlower setになることと同値．

証明

$k$ 次元面の1-skeltonが $k$ -正則なのは既に述べた．また $k$ 次元面が与えられたとき，そのnormal vectorをgenericな方向に少し回転させた方向を見ると，所望の向きづけが手に入る．

逆に後半が成立しているとする． $G[A]$ の唯一のsinkを $v$ とする． $v$ に向かう $k$ 本の辺を全て含む面 $F$ が存在する．good orientationなので，半順序において $F$ の要素は全て $v$ 以下．よって， $F \subset G[A$ ]であるが、ともに連結で $k$ -正則なので，これらは一致する．

コメント

simpleでない場合の反例としては複数のneighborly polytopeなどが挙げられるそうです。（まだ理解していません）
以下に色々情報源がありそうです。

pantodon.jp

link.springer.com