組合せ数学の雑記帳 第8回
「ハム・サンドイッチとネックレス」
前回はボルスク-ウラムの定理を用いたクネーザー予想の解決の証明を紹介しました。
(正確にはまだ予想の解決のための定理の半分ですが。)
今回の記事は、そのおまけ的なものをまとめた感じの内容でした。
まず、最初は、Bárányによるクネーザー予想の別証明の紹介です。
これは、とても短い証明で、最初にLovászが証明した論文と同じ論文誌に、
Lovászの次の論文として並べて掲載されています。
同じくボルスク-ウラムの定理を用いるのですが、近傍複体を経ることなく、直接
クネーザーグラフの彩色可能性を議論します。
クネーザーグラフはのサイズの部分集合を頂点として、
互いに交わりを持たないときに辺で結んだグラフ、そして、示したいことは
このグラフを色では彩色できないことを示すことでした。
Bárányの証明では、まず、次元球面上にの
点を配置します。
この際、Galeの補題というものを用い、のどの開半球も
この点のうちの点を含むようにうまく配置します。
ここで、次の形のボルスク-ウラムの定理を用います。
定理(開被覆版のボルスク-ウラムの定理)
次元球面が個の開集合で被覆されるとき、
いずれかのは必ず互いに対極点となる2点の組を含む。
が色で彩色できたとしましょう。
今考えている球面上の各点に対しては、その点を中心とする開半球
(原点からへのベクトルを法線ベクトルとする超平面でを切った半球の
を含む側の半球です)
が定まります。
この開半球内に色で彩色される頂点に対応するサイズの部分集合の要素となっている
点が含まれるようなをすべて集めた集合をとすると、
ゲールの補題を用いた点の配置方法により、はを被覆することが分かります。
これに対して開被覆版のボルスク-ウラムの定理を用いると、
あるが上の対極点の組とを含むことになります。
しかし、を中心とする開半球とを中心とする開半球は交わりを持たないので、
この2点が同じに入る、すなわち、この2つの開半球にそれぞれ含まれる2つの
サイズの部分集合に対応する頂点が同じ色で彩色されているというのはおかしいことになります。
(交わりを持たない2つのサイズの部分集合はにおいて辺で結ばれるので、
同じ色で彩色してはいけないはず。)
これがBárányの証明です。
このBárányの別証明は、前回の証明とはだいぶ見た目も理屈も違いますが、
同じボルスク-ウラムの定理が決め手になるというのは面白いところです。
次に、もう一つの関連する話題として、ハム・サンドイッチの定理を紹介しました。
これは有名な話で、次元空間中に個の集合(それぞれ可測で
有限値の測度を持つとする)があるとき、
ある1つの超平面でこの各々の集合を同時にそれぞれ2等分するものを見つけることができる、
という定理です。
離散幾何学ではこの各を有限個の点集合として与え、超平面の両側に同数の点が入るように
等分する超平面を探す、という形でよく利用されます。
この定理もボルスク-ウラムの定理から示されます。
そして、その応用として、ネックレス定理を紹介しました。
これは、種類の色の玉が適当な順番で1列に並んでいるネックレスがあるとして
(ネックレスは輪っかではなく、輪っかに留める前の切り開かれた線分上のものです)、
このネックレスの玉と玉の間の高々箇所を切り分け、生じる個の塊をうまく2人に
分けることにより、両者が各色の玉を同数ずつもらえるようにしたい、というのが問題で、
これがとすればいつでもこの切り分けが可能である、というのがネックレス定理です。
このネックレス定理は、ネックレスを次元空間の
モーメント曲線と呼ばれる曲線上に配置した上でハム・サンドイッチ定理を用いると証明されます。
ハム・サンドイッチ定理によって各色を等分することが保証されて、
モーメント曲線の性質により、切り口が高々個ということが保証される、というような仕組みです。
このネックレス定理の面白いところは、問題には全く幾何学的な要素がない組合せ的な問題である
にも関わらず、うまく幾何学的な配置を用いることで証明できるというところです。
(クネーザー予想の話もそうでした。)
また、今のところ、幾何学的な道具立てを用いない証明方法は知られていないようです。
最後に、ボルスク-ウラムの定理のいろいろな形の主張と、それらが等価であることがどのように
示せるかを簡単に記事の補足として載せて、前回から今回に続いた、ボルスク-ウラムの定理の
話は一段落、という形になりました。
戻る
八森正泰
hachi@sk.tsukuba.ac.jp
筑波大学システム情報系
(社会工学域)