ヘリーの定理
数学の離散幾何学の分野におけるヘリーの定理（ヘリーのていり、英: Helly's theorem）とは、凸集合がお互いに共通部分を持つ状況に関する基本的な結果である。エードゥアルト・ヘリーによって1913年に発見された[1]が、1923年まで出版されることはなく、その間に Radon (1921) や König (1922) によって代替的な証明が与えられていた。ヘリーの定理を元に、ヘリー族の概念が生まれた。
内容 編集
n > d とし、X1, ..., Xn を Rd の有限個の凸部分集合とする。それらの内 d+1 個の任意の集合の共通部分が空でないなら、全体の共通部分も空でない。すなわち
である。無限個の集まりに対しては、次のようにコンパクト性を仮定する必要がある：
{Xα} を Rd のコンパクトな凸部分集合の集まりとし、その濃度が高々 d+1 であるようなすべての部分集合の共通部分は空でないとする。このとき、全体の共通部分も空でない。
証明 編集
Radon (1921) の証明と同様に、ラドンの定理による有限の場合の証明を始めに行う。すると無限の場合は、コンパクト性を特徴付ける有限交差性によって従う。すなわち、コンパクト空間の閉部分集合の集まりの共通部分が空でないための必要十分条件は、すべての有限の部分的な集まりの共通部分が空でないことなのである（ある単一の集合を固定した際、その集合と他のすべての集合との共通部分は、ある固定されたコンパクト空間の閉部分集合である）。
証明は数学的帰納法によって行われる：
基本となる場合 n = d+2 とする。仮定より、任意の j = 1, ..., n に対して、Xi すべてと Xj の例外との共通部分に含まれる点 xj が存在する。今、A1 の凸包が A2 の凸包と交わる互いに素な部分集合 A1, A2 を持つ集合 A = {x1, ..., xn} に対して、ラドンの定理を適用する。p はそれら二つの凸包の共通部分にある点とする。次を示す：
実際、任意の j ∈ {1, ..., n} を考え、p ∈ Xj を示す。Xj に含まれない可能性のある唯一つの A の元は xj である。xj ∈ A1 であるなら、xj ∉ A2 であり、したがって Xj ⊃ A2 である。Xj は凸であるため、A2 の凸包を含み、したがって p ∈ Xj となる。同様に、xj ∉ A1 であるなら、Xj ⊃ A1 であり、したがって同様の理由で p ∈ Xj となる。p はすべての Xj に含まれるため、それらの共通部分に含まれるということになる。
上の例では、点 x1, ..., xn はすべて異なるものとして考えられていた。そうでない場合、すなわちある i ≠ k に対して xi = xk であるような場合、xi はすべての集合 Xj に含まれることとなり、再び共通部分は空でないと結論付けられる。以上で n = d+2 の場合は証明された。
帰納的な手順 n > d+1 とし、n−1 に対して定理の内容は成立しているものとする。上述の議論より、d+2 個の集合の任意の部分的な集まりは空でない共通部分を持つ。すると二つの集合 Xn−1 および Xn を単一の集合 Xn−1 ∩ Xn に置き換えた集合の集まりを考えることが出来る。そのような新たな集まりに対して、d+1 個の集合のすべての部分的な集まりは空でない共通部分を持つ。したがって帰納的な仮定を適用することが出来、そのような新たな集まりは空でない共通部分を持つことが示される。同様の手法を元の集まりに適用することで、証明は完成される。
関連項目 編集
脚注 編集
参考文献 編集
- Bollobás, B. (2006), “Problem 29, Intersecting Convex Sets: Helly's Theorem”, The Art of Mathematics: Coffee Time in Memphis, Cambridge University Press, pp. 90–91, ISBN 0-521-69395-0.
- Danzer, L.; Grünbaum, B.; Klee, V. (1963), “Helly's theorem and its relatives”, Convexity, Proc. Symp. Pure Math., 7, American Mathematical Society, pp. 101–179.
- Eckhoff, J. (1993), “Helly, Radon, and Carathéodory type theorems”, Handbook of Convex Geometry, A, B, Amsterdam: North-Holland, pp. 389–448.
- Heinrich Guggenheimer (1977) Applicable Geometry, page 137, Krieger, Huntington ISBN 0-88275-368-1 .
- Helly, E. (1923), “Über Mengen konvexer Körper mit gemeinschaftlichen Punkten”, Jahresbericht der Deutschen Mathematiker-Vereinigung 32: 175–176.
- König, D. (1922), “Über konvexe Körper”, Mathematische Zeitschrift 14 (1): 208–220, doi:10.1007/BF01215899.
- Radon, J. (1921), “Mengen konvexer Körper, die einen gemeinsamen Punkt enthalten”, Mathematische Annalen 83 (1–2): 113–115, doi:10.1007/BF01464231.