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

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

Твердження

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

\bigcap _{j=1}^{n}X_{j}\neq \varnothing .

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

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

Доведення

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

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

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

p\in \bigcap _{j=1}^{n}X_{j}.

Насправді, розглянемо будь-яке $j \in {1, ..., n}.$ ми доведемо, що $p \in X j .$ Зауважимо, що єдиний елемент з $A$ , що може бути не в $X j$ — це $x j$ . Якщо $x j \in A 1$ , тоді $x j \notin A 2$ , і отже $X j \supset A 2$ . З того, що $X j$ опукла, вона також містить опуклу оболонку $A 2$ і тому $p \in X j$ . Так само, якщо $x j \notin A 1$ , тоді $X j \supset A 1$ , і завдяки таким самим міркуванням $p \in X j$ . Тому, що $p$ лежить в кожному $X j$ , вона також має бути в їх перетині.

Вище, ми припустили, що всі точки $x 1, ..., x n$ різні. Якщо це не так, скажімо $x i = x k$ для деякого $i \neq k$ , тоді $x i$ належить кожній з множин $X j$ , і знов, ми заключаємо, що перетин не порожній. Це завершує доведення для $n = d 2$ .

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

Див. також

Нерв покриття

Примітки

↑ Danzer, Grünbaum та Klee, (1963).

Danzer, L.; Grünbaum, B.; Klee, V. (1963), Helly's theorem and its relatives, Convexity, Proc. Symp. Pure Math., т. 7, American Mathematical Society, с. 101—180.
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.

[1] Danzer, Grünbaum та Klee, (1963).

[1]