ヘリーの定理

ヘリーの定理

ヘリーの定理（Helly's theorem）は、数学の離散幾何学における重要な定理であり、凸集合に関連する共通部分の概念を扱っています。この定理は1913年にエードゥアルト・ヘリーによって発見されましたが、最初にその内容が公表されたのは1923年になってからでした。この間に、他の数学者であるラドンやクーニヒによっても、類似の証明がなされました。

定理の内容

ヘリーの定理は、次のような条件の下で成り立ちます：整数 n と次元 d において、n > d であるとします。ここで、X1, ..., Xn は、d次元ユークリッド空間 R^d 内の有限の凸部分集合を表します。もしこれらの集合内の d + 1 個の任意の部分集合の共通部分が空でないならば、全体の共通部分も空でないことを保証します。すなわち、次の条件が成り立ちます。

$$igcap_{j=1}^{n}X_{j}
eq ext{空集合}$$

また、無限集合については、コンパクト性を考慮する必要があります。すなわち、コンパクトな凸部分集合の集まり {Xα} があり、その中のすべての部分集合が d + 1 以下の濃度を持つ場合は、その共通部分も空でないということが示されます。

証明の概要

ヘリーの定理の証明は、ラドン (1921) による証明を基にしており、最初は有限の場合に関する証明から始まります。その後、無限の場合の結果はコンパクト性による有限交差性から導かれます。具体的には、コンパクト空間における閉部分集合の集まりの共通部分が空でないための必要条件は、すべての有限部分集合の共通部分が空でないことです。

証明は数学的帰納法を用いて実施されます。まず、基本的なケースとして n = d + 2 を考えます。この条件の下では、任意の集合 j に対して、Xj を除いた他のすべての集合との共通部分に点 xj が存在します。

さらに、集合 A に対して、その凸包が互いに交わるように A1 と A2 を選びます。ここで、p はこれらの二つの凸包が交わる点です。この時点において、次のことを示すことができます。

$$p ext{ は } igcap_{j=1}^{n}X_{j} に属する。$$

すべての j に対して、p が Xj に含まれることを確認します。もし Xj に含まれない唯一の点 xj が集合 A に含まれている場合、それによって contradiction を生じさせ、最終的にすべての Xj に点 p が含まれることが確認できます。このようにして、n = d + 2 の場合が証明されます。

次に、n > d + 1 という仮定の下、n − 1 に対してヘリーの定理の内容を適用します。n − 1 個の集合に対して、任意の部分集合には空でない共通部分が存在することが確立されているため、最後の Xn を含めた新しい集合を形成することで、元の集合に対しても同様の結果が適用できることが導かれます。

この帰納的手法によって、全ての n > d においてヘリーの定理が成立することが証明されます。

参考文献

• - Bollobás, B. (2006). “Problem 29, Intersecting Convex Sets: Helly's Theorem”, The Art of Mathematics: Coffee Time in Memphis, Cambridge University Press.
• - Danzer, L.; Grünbaum, B.; Klee, V. (1963). “Helly's theorem and its relatives”, Convexity, Proc. Symp. Pure Math., American Mathematical Society.
• - Eckhoff, J. (1993). “Helly, Radon, and Carathéodory type theorems”, Handbook of Convex Geometry.
• - Helly, E. (1923). “Über Mengen konvexer Körper mit gemeinschaftlichen Punkten”, Jahresbericht der Deutschen Mathematiker-Vereinigung.
• - Radon, J. (1921). “Mengen konvexer Körper, die einen gemeinsamen Punkt enthalten”, Mathematische Annalen.

もう一度検索