Теорема Хеллі

Теорема Хеллі — це базовий результат в дискретній геометрії щодо перетину опуклих множин. Вона була відкрита Едвардом Хеллі у 1913,[1] але не опублікована до 1923, на той момент вже з'явились альтернативні доведення Radon, (1921) і König, (1922). Теорема Хеллі дає початок сім'ї Хеллі.

Теорема Хеллі для Евклідової площини: якщо сім'я опуклих множин має непорожній перетин для кожної трійки множин, тоді вся сім'я має непорожній перетин.

Твердження

Нехай X1, ..., Xn буде скінченною колекцією опуклих підмножин Rd, з n > d. Якщо перетин кожних d + 1 з цих множин непорожній, тоді вся колекція має непорожній перетин; тобто

Для нескінченної колекції треба припустити компактність:

Нехай {Xα} буде колекцією компактних опуклих підмножин Rd, таких що кожна підколекція потужності не більше d + 1 має непорожній перетин. Тоді вся колекція має непорожній перетин.

Доведення

Ми доведемо скінченну версію використовуючи теорему Радона як в доведенні Radon, (1921). Нескінченна версія слідує з критерію властивості скінченного перетину компактності: колекція замкнутих підмножин компактного простору має непорожній перетин тоді і тільки тоді якщо кожна скінченна підколекція має непорожній перетин (щойно ми зафіксували одну множину, перетин усіх інших з нею це певний компактний простір).

Доведення за індукцією:

База: Нехай n = d + 2. Згідно з нашими припущеннями, для кожного j = 1, ..., n існує точка xj, яка є перетином всіх Xi можливо без Xj. Тут ми застосовуємо теорему Радона до множини A = {x1, ..., xn}, яка дає нам неперетинні підмножини A1, A2 множини A, такі що опукла оболонка для A1 перетинає опуклу оболонку для A2. Припустимо, що p — це точка в перетині цих опуклих оболонок. Ми стверджуємо, що

Насправді, розглянемо будь-яке j ∈ {1, ..., n}. ми доведемо, що pXj. Зауважимо, що єдиний елемент з A, що може бути не в Xj — це xj. Якщо xjA1, тоді xjA2, і отже XjA2. З того, що Xj опукла, вона також містить опуклу оболонку A2 і тому pXj. Так само, якщо xjA1, тоді XjA1, і завдяки таким самим міркуванням pXj. Тому, що p лежить в кожному Xj, вона також має бути в їх перетині.

Вище, ми припустили, що всі точки x1, ..., xn різні. Якщо це не так, скажімо xi = xk для деякого ik, тоді xi належить кожній з множин Xj, і знов, ми заключаємо, що перетин не порожній. Це завершує доведення для n = d + 2.

Крок: Припустимо, що n > d + 2 і, що твердження дотримується для n−1. Довід наведений вище показує, що будь-яка підколекція з d + 2 множин має непорожній перетин. Тоді ми можемо розглянути колекцію де дві множини Xn−1 і Xn замінені на одну множину Xn−1Xn. У цій новій колекції, кожна підколекція з d + 1 множин має непорожній перетин. Тому ми можемо застосувати індуктивну гіпотезу і показати, що нова колекція має непорожній перетин. З цього випливає, що початкова колекція має непорожній перетин, що завершує доведення.

Див. також

Примітки

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.