組合せ数学の雑記帳 第8回

「ハム・サンドイッチとネックレス」

前回はボルスク-ウラムの定理を用いたクネーザー予想の解決の証明を紹介しました。 (正確にはまだ予想の解決のための定理の半分ですが。) 今回の記事は、そのおまけ的なものをまとめた感じの内容でした。

まず、最初は、Bárányによるクネーザー予想の別証明の紹介です。 これは、とても短い証明で、最初にLovászが証明した論文と同じ論文誌に、 Lovászの次の論文として並べて掲載されています。 同じくボルスク-ウラムの定理を用いるのですが、近傍複体を経ることなく、直接 クネーザーグラフの彩色可能性を議論します。 クネーザーグラフK2n+k,n{1,2,,2n+k}のサイズnの部分集合を頂点として、 互いに交わりを持たないときに辺で結んだグラフ、そして、示したいことは このグラフをk+1色では彩色できないことを示すことでした。

Bárányの証明では、まず、k次元球面Sk上に{1,2,,2n+k}2n+k点を配置します。 この際、Galeの補題というものを用い、Skのどの開半球も この2n+k点のうちのk点を含むようにうまく配置します。

ここで、次の形のボルスク-ウラムの定理を用います。

定理(開被覆版のボルスク-ウラムの定理)
d次元球面Sdd+1個の開集合U1,,Ud+1で被覆されるとき、 いずれかのUiは必ず互いに対極点となる2点の組を含む。

KG2n+k,nk+1色で彩色できたとしましょう。 今考えている球面Sk上の各点xに対しては、その点xを中心とする開半球 (原点からxへのベクトルを法線ベクトルとする超平面でSkを切った半球の xを含む側の半球です) が定まります。 この開半球内に色iで彩色される頂点に対応するサイズnの部分集合の要素となっている n点が含まれるようなxをすべて集めた集合をUiとすると、 ゲールの補題を用いた点の配置方法により、U1,,Uk+1Skを被覆することが分かります。 これに対して開被覆版のボルスク-ウラムの定理を用いると、 あるUiSk上の対極点の組xxを含むことになります。 しかし、xを中心とする開半球とxを中心とする開半球は交わりを持たないので、 この2点が同じUiに入る、すなわち、この2つの開半球にそれぞれ含まれる2つの サイズnの部分集合に対応する頂点が同じ色iで彩色されているというのはおかしいことになります。 (交わりを持たない2つのサイズnの部分集合はKG2n+k,nにおいて辺で結ばれるので、 同じ色で彩色してはいけないはず。) これがBárányの証明です。

このBárányの別証明は、前回の証明とはだいぶ見た目も理屈も違いますが、 同じボルスク-ウラムの定理が決め手になるというのは面白いところです。

次に、もう一つの関連する話題として、ハム・サンドイッチの定理を紹介しました。 これは有名な話で、d次元空間中にd個の集合A1,A2,,Ad(それぞれ可測で 有限値の測度を持つとする)があるとき、 ある1つの超平面でこの各々の集合Aiを同時にそれぞれ2等分するものを見つけることができる、 という定理です。 離散幾何学ではこの各Aiを有限個の点集合として与え、超平面の両側に同数の点が入るように 等分する超平面を探す、という形でよく利用されます。 この定理もボルスク-ウラムの定理から示されます。

そして、その応用として、ネックレス定理を紹介しました。 これは、n種類の色の玉が適当な順番で1列に並んでいるネックレスがあるとして (ネックレスは輪っかではなく、輪っかに留める前の切り開かれた線分上のものです)、 このネックレスの玉と玉の間の高々k箇所を切り分け、生じるk+1個の塊をうまく2人に 分けることにより、両者が各色の玉を同数ずつもらえるようにしたい、というのが問題で、 これがk=nとすればいつでもこの切り分けが可能である、というのがネックレス定理です。

このネックレス定理は、ネックレスをn次元空間の モーメント曲線と呼ばれる曲線上に配置した上でハム・サンドイッチ定理を用いると証明されます。 ハム・サンドイッチ定理によって各色を等分することが保証されて、 モーメント曲線の性質により、切り口が高々n個ということが保証される、というような仕組みです。

このネックレス定理の面白いところは、問題には全く幾何学的な要素がない組合せ的な問題である にも関わらず、うまく幾何学的な配置を用いることで証明できるというところです。 (クネーザー予想の話もそうでした。) また、今のところ、幾何学的な道具立てを用いない証明方法は知られていないようです。

最後に、ボルスク-ウラムの定理のいろいろな形の主張と、それらが等価であることがどのように 示せるかを簡単に記事の補足として載せて、前回から今回に続いた、ボルスク-ウラムの定理の 話は一段落、という形になりました。

戻る

八森正泰
hachi@sk.tsukuba.ac.jp
筑波大学システム情報系 (社会工学域)