More Web Proxy on the site http://driver.im/

papatagonian’s blog

互いに接するd-単体の最大値

はじめての投稿です。問題から始まる記事を書こうと思います。

問題

次元単体が $\mathbb{R}^d$ の中に個ある．どの二つも内部を共有せず，境界も含めるとどの二つも d-1 次元の交わりを持つ．としてあり得る最大値 f(d) はいくらか．

d=2 の時を考える．つの三角形を条件を満たすように配置することはできる．一方，つの三角形が条件を満たすように配置できるとすると，その双対グラフが K_5 の平面的な埋め込みになってしまう．したがって f(2)=4 である．

以下が知られている．証明もとても初等的である．

定理 [Perles 84]

$f(d) \leq 2^{d+1}$

証明

上の性質を満たす個の単体 $P_1, \ldots, P_k$ があるとする．いずれかの単体のfacetを含む超平面を列挙したものが $H_1, \ldots, H_s$ だとする． H_i の定める閉半空間を H_i^+, H_i^- とする（好きなように向きを決めていい）．

これをもとに $k \times s$ 行列を次で定める．

超平面がのfacetを含み，かつがに含まれるとき， $M_{ij} = 1$ ．
超平面がのfacetを含み，かつがに含まれるとき， $M_{ij}= -1$ ．
そうでないとき $M_{ij}=0$ ．

この時次が成り立っている．

どの行も非ゼロ成分の数はfacetの数に等しく，個．
どの二つの行についても，一方で，もう一方でとなっている列がある（対応する単体を分けている超平面があるため）．

このから巨大な行列を次のように作る．

各行ベクトルについて，現れるをかで置き換えて得られるものを全て列挙して並べる．
それらを全て並べる．

すると，上の1つ目の性質よりのサイズは $k2^{s-d-1} \times s$ となる．さらに上の2つ目の性質からの全ての行ベクトルは異なることがわかる．よって， $ks^{s-d-1} \leq 2^s$ となり，定理がしたがう．

以上

コメント

$f(d) \geq 2^d$ も示されています．これも面白いのでいつか紹介します．
かは未解決のようです．つまり冒頭の問題は未解決問題のようです．

参考文献

Touching Simplices and Polytopes: Perles’ argument | Combinatorics and more

Touching simplices | SpringerLink