Hellysova věta - Hellys theorem - Wikipedia

Hellyho věta pro euklidovskou rovinu: má-li rodina konvexních množin neprázdnou křižovatku pro každou trojici množin, pak má celá rodina neprázdnou křižovatku.

Hellyho věta je základní výsledek v diskrétní geometrie na průsečík z konvexní sady. Objevil jej Eduard Helly v roce 1913,^[1] ale nebyl jím publikován až do roku 1923, do té doby alternativní důkazy Radon (1921) a König (1922) se už objevil. Hellyho věta dala vzniknout představě a Helly rodina.

Prohlášení

Nechat $X 1, ..., X n$ být konečnou sbírkou konvexních podmnožin $R d$ , s $n > d + 1$ . Pokud je průsečík každého $d + 1$ z těchto sad je neprázdné, pak má celá kolekce neprázdnou křižovatku; to je

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

U nekonečných sbírek je třeba předpokládat kompaktnost:

Nechat ${X α}$ být sbírkou kompaktní konvexní podmnožiny $R d$ , takže každá podkolekce mohutnost nejvíce $d + 1$ má neprázdnou křižovatku. Pak má celá kolekce neprázdnou křižovatku.

Důkaz

Konečnou verzi dokazujeme pomocí Radonova věta jako v dokladu od Radon (1921). Nekonečná verze pak následuje vlastnost konečné křižovatky charakterizace kompaktnost: kolekce uzavřených podskupin kompaktního prostoru má neprázdný průnik právě tehdy, když má každá konečná podkolekce neprázdný průnik (jakmile opravíte jednu sadu, průsečík všech ostatních s ní jsou uzavřené podskupiny pevné kompaktní prostor).

Důkaz je indukce:

Základní případ: Nechat $n = d + 2$ . Podle našich předpokladů pro každého $j = 1, ..., n$ má to smysl $X j$ to je ve společné křižovatce všech $X i$ s možnou výjimkou $X j$ . Nyní použijeme Radonova věta do sady $A = {X 1, ..., X n},$ který nám poskytuje nesouvislé podmnožiny $A 1, A 2$ z $A$ takové, že konvexní obal z $A 1$ protíná konvexní trup $A 2$ . Předpokládejme to $p$ je bod v průsečíku těchto dvou konvexních trupů. Tvrdíme to

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

Skutečně zvažte $j \in {1, ..., n}.$ To dokážeme $p \in X j .$ Všimněte si, že jediný prvek $A$ to nemusí být v $X j$ je $X j$ . Li $X j \in A 1$ , pak $X j \notin A 2$ , a proto $X j \supset A 2$ . Od té doby $X j$ je konvexní, pak také obsahuje konvexní trup $A 2$ a proto také $p \in X j$ . Stejně tak, pokud $X j \notin A 1$ , pak $X j \supset A 1$ , a ze stejného důvodu $p \in X j$ . Od té doby $p$ je v každém $X j$ , musí být také v křižovatce.

Nahoře jsme předpokládali, že body $X 1, ..., X n$ jsou všechny odlišné. Pokud tomu tak není, řekněme $X i = X k$ pro některé $i \neq k$ , pak $X i$ je v každé ze sad $X j$ , a opět jsme dospěli k závěru, že křižovatka je neprázdná. Tím je dokončen důkaz v případě $n = d + 2$ .

Indukční krok: Předpokládat $n > d + 2$ a že tvrzení platí pro $n -1$ . Výše uvedený argument ukazuje, že jakákoli podkolekce $d + 2$ sady budou mít neprázdnou křižovatku. Poté můžeme zvážit kolekci, kde nahradíme dvě sady $X n -1$ a $X n$ s jedinou sadou $X n -1 \cap X n$ . V této nové kolekci každá podkolekce $d + 1$ sady budou mít neprázdnou křižovatku. Indukční hypotéza proto platí a ukazuje, že tato nová kolekce má neprázdnou křižovatku. To znamená totéž pro původní kolekci a doplňuje se důkaz.

Barevná věta Helly

The barevná Hellyho věta je rozšířením Hellyho věty, ve které místo jedné sbírky existuje d+1 kolekce konvexních podskupin $R d$ .

Pokud, pro každý výběr a příčný - jedna sada z každé sbírky - pro všechny vybrané sady je společný bod, pak pro aspoň jeden kolekcí je společný bod pro všechny sady v kolekci.

Obrazně lze uvažovat o d+1 sbírky k d+1 různé barvy. Potom věta říká, že pokud má každá volba jedné sady na barvu neprázdnou křižovatku, pak existuje barva taková, že všechny sady této barvy mají neprázdnou křižovatku.^[2]

Frakční Hellyho věta

Pro každého A > 0 nějaké jsou b > 0 takové, že pokud $X 1, ..., X n$ jsou n konvexní podmnožiny $R d$ a alespoň A-frakce (d+1) - n-tice množin mají společný bod, potom alespoň zlomek b sady mají společný bod.^[2]

Viz také

Carathéodoryova věta
Kirchbergerova věta
Lemma Shapley – Folkman
Kerin – Milmanova věta
Choquetova teorie
Radonova věta a jeho zobecnění, Tverbergova věta

Poznámky

^ Danzer, Grünbaum & Klee (1963).
^ ^A ^b Kalai, Gil (2019-03-15), „Zprávy o frakční Helly, barevné Helly a Radonu“, Kombinatorika a další, vyvoláno 2020-07-13

Reference

Bollobás, B. (2006), „Problém 29, Protínající se konvexní množiny: Hellyho věta“, The Art of Mathematics: Coffee Time in Memphis, Cambridge University Press, str. 90–91, ISBN 0-521-69395-0.
Danzer, L .; Grünbaum, B.; Klee, V. (1963), „Hellyho věta a její příbuzní“, Konvexnost, Proc. Symp. Čistá matematika., 7, Americká matematická společnost, str. 101–180.
Eckhoff, J. (1993), „Věty typu Helly, Radon a Carathéodory“, Příručka konvexní geometrie, A, B, Amsterdam: Severní Holandsko, s. 389–448.
Heinrich Guggenheimer (1977) Použitelná geometrie, strana 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.

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

[:0-2] A ^b Kalai, Gil (2019-03-15), „Zprávy o frakční Helly, barevné Helly a Radonu“, Kombinatorika a další, vyvoláno 2020-07-13

[1]

[2]