2023-05-15

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を与えます。

2023-05-10

極値組合せ論における外積代数的手法

次のような極値組合せ論のBollabas*1の結果を紹介します。

定理

$n,p,q$ を $n \geq p+q$ なる自然数とする。 $A_1,\ldots,A_k,B_1,\ldots,B_k \subseteq \{1,\ldots,n\}$ が以下を満たしているとする。

各 $i$ について $|A_i| \leq p, |B_i| \leq q$ .
各 $i$ について $A_i \cap B_i = \emptyset.$
$1 \leq i \lt j \leq k$ ならば、 $A_i \cap B_j \neq \emptyset.$

このとき、 $k \leq \binom{p+q}{p}$ が成り立つ。

ちなみに定理内の上界を等号で達成する例として、 $\{(A,B) : A \subset \{1,\ldots,p+q\}, |A|=p, B=\{1,\ldots,p+q\}-A\}$ があります。

linear algebraic methodの中でも外積代数を用いた非常に綺麗な証明があります。

証明

必要ならば $A_i$ や $B_i$ に適当に元を加えることで、各 $i$ について $|A_i|=p, |B_i|=q$ という仮定の下で定理を示せばよい。

$v_1,\ldots,v_n \in \mathbb{R}^{p+q}$ であって、どの $p+q$ 個も線型独立であるようなものを固定する。 $s_i:=\bigwedge_{e \in A_i} v_e \in \mathbb{R}^{\binom{p+q}{p}}, t_i:=\bigwedge_{a \in B_i}v_e \in \mathbb{R}^{\binom{p+q}{q}}$ とする。すると、仮定より

$i$ について、 $s_i \wedge t_i\neq 0$
$1 \leq i \lt j \leq n$ について、 $s_i \wedge t_j=0$

が成立する。 $s_1, \ldots, s_k$ が線型独立であるならば、 $k \leq \dim \mathbb{R}^{\binom{p+q}{p}}=\binom{p+q}{p}$ が従う。これらが線形独立なことは、 $\sum c_i s_i=0$ なる非ゼロ係数が存在したとすると、最後の非ゼロ成分が $c_j$ であるとすると、 $(\sum c_i s_i)\wedge t_j=c_j s_j \wedge t_j=0$ となり矛盾することから分かる。

コメント

skew-Bollabasの定理とよばれているようです。オリジナルのBollabasの結果は二つ目の条件を「相異なる[\tex: i,j]について」と弱めたもののようです。skew-Bollabasの定理を使う証明はset-pair methodとよばれるようです。
私はMatousekの本
https://kam.mff.cuni.cz/~matousek/stml-53-matousek-1.pdf
で昔ちらっと見かけていたのですが、下の本で、単体的凸多面体の上限定理の証明で使われているのを見つけテンションが上がっていました。次のような議論です。
- 単体複体 $\Delta$ にpartition $\Delta = \coprod [G_i:F_i$ ]が存在するとき、 $B_i:=G_i, A_i:=V(\Delta)-F_i$ は定理の条件を満たす。したがって、skew-Bollabasの定理から、hベクトルの途中までの和を上から評価することができる。実はfベクトルは、hベクトルの途中までの和たちの非負結合で書けるので、fベクトルの上界が得られる。
  www.kyoritsu-pub.co.j

*1:恥ずかしながらmardownでの人名のアクセント記号が分からず、アクセント記号なしで表記します。

2023-02-17

多面体版Stokesの定理

3週間くらい全然記事を書けていませんでした。というかアクセス解析をしてもアクセス0のこのブログを書き続ける理由などあるのでしょうか。だからこそ自由に書けるというメリットがあるのだみたいな論理で納得させています。長いものを紹介するのはハードルが高いので、shortな話になります。というか、この記事は特に質が低いので、削除するかもしれません。

最近ふと見つけた公開講座の語り口が敬体でとてもフィット感があったので、今日はそのようにいきたいと思います。

定理

凸多面体 $P$ を考えます。 $P$ の各ファセット $F$ 毎に、次のようにベクトル $v_F$ を定めます。

$v_F$ は $F$ に垂直で外向きである。
$v_F$ の長さは各面 $F$ の[d-1]次元体積に等しい。

このとき， $\sum_{F} v_F=0$ となる。

余談

3次元版の問題をPeter Winklerの本で高校生の時に見て、一応解答を見たものの納得できなかった覚えがあります。

www.nippyo.co.jp

今となってはStokesの定理だねという主張です。が、正直積分とか忘れてしまって、どうやってStokesの定理を証明するんだったか思い出せません。恥ずかしい話ですが。

最近Lovaszの本を読んでる時に遭遇したので、懐かしくなりました。

bookstore.ams.org

証明

まず凸多面体は単体に分割できます（例えば、内部に点を取って、この点を頂点とし各ファセットを底面とする錐に分割すると、次元に関する帰納法から示せます）。よって、特殊ケースである単体について示せば良いです。

残された単体のケースですが、ちょうどいい線形代数の問題くらいなので、よかったら考えてみてください。

2023-01-29

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の結果はこれから直ちに従います。

2023-01-21

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

2023-01-15

教科書が読めない自分

できれば毎週末投稿をしたいと思っていましたが、今週は何か特別紹介したいことがないので、適当に思っていることを書きます。

僕は勉強する時に教科書っぽい本があまり読めません。その代わり、短めの話題を集めたようなものを好き勝手読んだりしています。

proofsfromthebook.github.io

https://kam.mff.cuni.cz/~matousek/stml-53-matousek-1.pdf

この辺です。ただ、結局、網羅的な力がついてるような気がしません。でも頑張って教科書スタイルの網羅的な本を読もうと思ってもどこかでつまづきます。院生の間はそんなことを何度も繰り返して、結局実力が付かないなあと思って、うまくいきませんでした。どうしたらいいのでしょう。

もう結構な歳なのに、学習法で悩んでいます。。。

以上です。

2023-01-07

奇次数グラフのハミルトン閉路の数に関するSmith Network Theorem

かなりニッチな話題を紹介します．

定理(Smith)

無向グラフ $G$ がある．次数が偶数の頂点は $i, j$ のみで，それ以外の頂点の次数は奇数である．このとき $i,j$ を両端に持つハミルトンパスは偶数個である．

証明

$G$ から補助グラフ $\mathcal{H}$ を次のように作る．

$\mathcal{H}$ の頂点集合は $i$ を端点にもつハミルトンパス全体．
$P,Q \in V(\mathcal{H})$ が隣接するのは， $| P \Delta Q |=2$ のときのみ．

各 $P \in V(\mathcal{H})$ には $i$ でない方の端点のラベルをつけておく．

$P \in V(\mathcal{H})$ がある $Q \in V(\mathcal{H})$ と隣接するとき， $P$ にある $e \in E(G)$ を加えたものから別の辺を一つ取り除いたものが $i$ を端点とするハミルトンパスになる．このようなことは $e$ が $P$ のラベルに接続するときのみ起こる．
逆に $e \not\in P$ が $P$ のラベルに接続する場合， $P \cup \{e\}$ から辺を一つ取り除いて $P$ 以外の $i$ を端点とするハミルトンパスを作る方法はちょうど $1$ つ．

したがって， $P \in V(\mathcal{H})$ の次数は，そのラベルの $G$ における次数より $1$ 小さい値に等しい．よって $\mathcal{H}$ において， $j$ のラベルのついた頂点のみ奇数次数でそれ以外のラベルのついた頂点は偶数次数．そのため $j$ のラベルがついた頂点は偶数個となる．

参考文献

http://homepage.tudelft.nl/64a8q/papers/handshake.pdf