Лема Віталі про покриття

Зверху початкова сім'я куль. Зеленим виділені кулі, що не перетинаються, синім - всі інші. Нижче та ж діаграма, в якій зелені кулі потроєні - зауважимо, що вони покривають всі сині кулі.

Лема Віталі про покриттях — твердження у комбінаторній геометрії, що широко використовується в теорії міри.

Лема використовується в доведенні теореми Віталі про покриття, але також має самостійний інтерес. Названа на честь італійського математика Джузеппе Віталі.

Формулювання

Скінченна версія

Нехай $B_1,\dots ,B_n$ — скінченна множина куль, що містяться в d-вимірному евклідовому просторі R^d (або, в більш загальному випадку, в довільному метричному просторі). Тоді існує підмножина $B_{j_1},B_{j_2},\dots ,B_{j_m}$ з цих куль, в якій кулі попарно не перетинаються, і виконується

$B_1\cup B_2\cup \dots \cup B_n\subseteq 3B_{j_1}\cup 3B_{j_2}\cup \dots \cup 3B_{j_m},$

де $3B_{j_k}$ позначає кулю з тим же центром, що і у $B_{j_k}$, але з втричі більшим радіусом радіусом.

Доведення

Припустимо, що множина куль є непорожньою, тобто n > 0. Нехай $B_{j_1}$ буде кулею із найбільшим радіусом. За індукцією, нехай обрано кулі $B_{j_1},\dots ,B_{j_k}.$ Якщо існують кулі із $B_1,\dots ,B_n,$ які не перетинаються із жодною із $B_{j_1}\cup B_{j_2}\cup \cdots \cup B_{j_k}$, то виберемо як $B_{j_{k+1}}$ таку кулю із найбільшим можливим радіусом. Якщо таких куль немає, то приймаємо m := k і завершуємо процес.

Позначимо $X:=\bigcup _{k=1}^{m}3B_{j_k}$ і доведемо, що $B_i\subset X$ для всіх $i=1,2,\dots ,n$. Це твердження є очевидним для $i\in \{j_1,\dots ,j_m\}$. В іншому випадку існує деяке $k\in \{1,\dots ,m\}$ для якого B_i перетинає $B_{j_k}$ і радіус кулі $B_{j_k}$ є не меншим, ніж B_i. З нерівності трикутника тоді випливає, що $B_i\subset 3B_{j_k}\subset X$, що завершує доведення.

Нескінченна версія

Нехай $\{B_j\mid j\in J\}$ — довільна (зліченна або незліченна) множина куль в R^d (або, більш загально, в сепарабельному метричному просторі), для якої

$\sup \{\mathrm{r}\mathrm{a}\mathrm{d}(B_j)\mid j\in J\}<\mathrm{\infty },$

де $\mathrm{r}\mathrm{a}\mathrm{d}(B_j)$ позначає радіус кулі B_j. Тоді для будь-якого $k>3$ існує зліченна підмножина

$\{B_j\mid j\in J{\text{'}}_k\},J{\text{'}}_k\subset J,$

куль, що попарно не перетинаються і

$\bigcup _{j\in J}{B}_j\subseteq \bigcup _{j\in J{\text{'}}_k}k{B}_j.$

Доведення

Нехай F позначає сім'ю всіх куль B_j, j ∈ J у твердженні леми про покриття. Нехай необхідна підсім'я G у F позначається також за допомогою $\{B_j,j\in J^{\prime }\}.$

Доведемо більш точне твердження леми. Нехай F є сім'єю невироджених куль у метричному просторі з обмеженим радіусом. Тоді існує підсім'я G така, що кожна куля B у F має непустий перетин із деякою кулею C у G для якої B ⊂ 5 C. Для сепарабельних метричних просторів (наприклад евклідових просторів) до того ж G є не більш, ніж зліченною.

Нехай R є супремумом радіусів куль із F. Розглянемо розбиття F на F_n, n ≥ 0, що складаються із куль B  радіуси яких належать проміжку (2⁻ⁿ⁻¹R, 2⁻ⁿR]. Можна розглянути послідовність сімей куль G_n, де G_n ⊂ F_n. Спершу позначимо H₀ = F₀ і G₀ деяку максимальну сім'ю куль із H₀, що попарно не перетинаються. Для сепарабельного метричного простору очевидно, що G₀ є не більш, ніж зліченною . Припускаючи, що G₀,...,G_n вже визначені, нехай

${𝐇}_{n+1}=\{B\in {𝐅}_{n+1}:B\cap C=\mathrm{\varnothing },\mathrm{\forall }C\in {𝐆}_0\cup {𝐆}_1\cup \dots \cup {𝐆}_n\},$

і нехай G_n+1 є максимальною сім'єю куль із H_n+1, що попарно не перетинаються. Для сепарабельного метричного простору G_n+1 є не більш, ніж зліченною. Тоді підсім'я

$𝐆:=\bigcup _{n=0}^{\mathrm{\infty }}{𝐆}_n$

із F задовольняє вказане точне твердження леми: G є сім'єю куль, що попарно не перетинаються і кожна куля B ∈ F перетинає кулю C ∈ G для якої B ⊂ 5 C. Справді, нехай B належить F_n. Тоді або B  не належить H_n, звідки n > 0 і B має непустий перетин із G₀,...,G_n−1 або B ∈ H_n і з максимальності G_n випливає, що B має непустий перетин із деякою кулею із G_n. У будь-якому випадку B має непустий перетин із кулею C, що належить об'єднанню G₀,...,G_n. Радіус кулі C є більшим 2⁻ⁿ⁻¹R, а радіус B не більшим 2⁻ⁿR, а тому B ⊂ 5 C випливає з нерівності трикутника. Для сепарабельного метричного простору G є зліченною множиною, як зліченне об'єднання зліченних множин.

Зауваження

• У доведенні нескінченної версії у означенні F_n замість 2⁻ⁿ можна використати c⁻ⁿ, c > 1. Тоді замість 5 можна використати константу 1 + 2c. Тобто у твердженні леми про покриття можна замість 5 взяти довільну константу більшу 3.
• У нескінченній версії лема перестає бути вірною, якщо радіуси не є обмеженими: наприклад, це невірно для нескінченної множини куль з цілими додатними радіусами і єдиним центром.
• У найзагальнішому випадку, для довільного метричного простору, вибір максимальної підмножини куль вимагає деякої форми леми Цорна.

Наслідки

• У будь-якому скінченному наборі куль $n$-вимірного евклідового простору, об'єднання яких має об'єм $V$, можна вибрати підмножину куль, що не перетинаються між собою із загальним об'ємом не меншим $\frac{1}{3^n}\cdot V$.
  • Коефіцієнт $\frac{1}{3^n}$ не є оптимальним і оптимальне значення не є відомими.

Література

• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation
• Шаблон:Citation.
• Шаблон:Cite book.
• Шаблон:Citation.