d-多面体のグラフのd-連結性

最近ようやく症状に気づいたのですが、以前は組合せ論周りで面白そうだと思うことがあまりにも多すぎて収集がつかなくなっていたようです。それも当然で、problem facingな分野であることは間違い無いですが、論文を書くまで至るにはある程度の流れを汲む必要があったりするのかもしれません。

何か毎週末書こうと思って始めたこのブログですが、ただ散文的に面白い結果を集めるのは何か違うような気がしています。また自分の時間も限られているので、このブログに何か書くためだけに情報を入れるのも違うように思います。とにかく普通に有意義に使っていきたいです。

今日はある結果を紹介します。一見脈絡がないように思えますが、実は無理矢理遠回りすればrigidityの結果の系としても得られるので、この先の記事の布石になるかもしれません。

定理[Balinski '61]

$d$ 次元凸多面体 $P$ のグラフ $G(P)$ は $d$ -連結

証明

$P$ の頂点を $v_1, \ldots, v_n$ とする． $d-1$ 点 $S \subset V(P)$ を任意にとり固定する． $S$ を取り除いても残りが連結であることを示す．場合分けをする．

$S$ があるproper face $F$ に含まれる場合

$F$ 上で最小値をとる一次関数 $\varphi$ をとる． $\text{argmax}_{P} \varphi$ は $P$ のあるface $F_1$ になる． $F_1$ 上にない $P$ の頂点は必ず $\varphi$ の値が自分より大きい頂点と隣接している．よってこれを繰り返すと必ず $F_1$ の頂点に辿り着く．

$S$ がどのproper faceにも含まれない場合

適当に頂点 $v \in V \setminus S$ を取る． $S$ および $v$ を通る超平面 $H$ を取る．この法線ベクトル方向の一次関数 $\varphi$ を考える． $S$ の点を全て通る支持超平面は存在しないので， $H$ の両側に頂点が存在し， $v$ はその両方に隣接している．一つ目の場合の議論と同様にして $H$ の両サイドはそれぞれ連結なので，全体として連結．

コメント

最初に言った話でより強くrigidityの結果の系になります。

定理[Whiteley]

$d$ -次元凸多面体のグラフは $d$ -rigid

サイズ $d-1$ のseparatorがあるとそれをヒンジにして回せるので、 $d$ -rigidなことに反します。よってBalinskiの結果はこれから直ちに従います。