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

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

 

問題

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

 

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

 

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

 

定理 [Perles 84]

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

 

証明

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

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

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

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

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

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

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

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

以上

 

 

コメント

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

参考文献

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

Touching simplices | SpringerLink