Slunečnice (matematika) - Sunflower (mathematics)
v matematika, a slunečnice nebo -Systém[1] je sbírka sady jehož párové průsečík je konstantní. Tato konstantní křižovatka se nazývá jádro slunečnice.
Hlavní výzkumná otázka týkající se slunečnic zní: za jakých podmínek existují a velký slunečnice (slunečnice s mnoha sadami)? The -lemma, slunečnicové lemma, a slunečnicová domněnka poskytnout různé podmínky, které naznačují existenci velké slunečnice v dané kolekci sad.
Formální definice
Předpokládat je nastavený systém, tj. sbírka podmnožiny sady . Sbírka je slunečnice (nebo -Systém) pokud existuje podmnožina z takové, že pro každého odlišný a v , my máme . Jinými slovy, je slunečnice, je-li průsečík každé sady v je konstantní. Všimněte si, že tato křižovatka, , možná prázdný; sbírka disjunktní podmnožiny je také slunečnice.
Slunečnicové lemma a domněnka
Erdős & Rado (1960, str. 86) prokázal slunečnicové lemma, s uvedením, že pokud a jsou pozitivní celá čísla pak sbírka množiny mohutnosti nanejvýš obsahuje slunečnici s více než sady.
The slunečnicová domněnka je jednou z několika variant domněnky Erdős & Rado (1960, str. 86) že faktor lze nahradit pro nějakou konstantu . Dokument Alweissa, Lovetta, Wu a Zhanga z roku 2020 poskytuje nejlepší pokrok směrem k domněnce, což dokazuje výsledek pro (Alweiss a kol. 2020 ).[2]
Analogový pro nekonečné kolekce sad
The -lemma uvádí, že každý nespočet sbírka konečné množiny obsahuje nespočet -Systém.
The -lemma je kombinační set-teoretický nástroj používaný v důkazech k uložení horní hranice na velikosti kolekce párově nekompatibilních prvků v a nutit poset. Může být například použit jako jedna ze složek v důkazu, že je v souladu s Teorie množin Zermelo – Fraenkel že hypotéza kontinua nedrží. To bylo představeno Shanin (1946 ).
Li je - velká sbírka počitatelný podmnožiny , a pokud platí hypotéza kontinua, pak existuje - velikost -podsystém. Nechat vyjmenovat . Pro , nechť . Podle Fodorovo lemma, opravit stacionární v takhle se neustále rovná na .Stavět z mohutnost tak, že kdykoli jsou v pak . Pomocí hypotézy kontinua existují pouze - mnoho spočetných podmnožin , takže dalším ředěním můžeme stabilizovat jádro.
Viz také
Reference
- Alweiss, Ryan; Lovett, Shachar; Wu, Kewen; Zhang, Jiapeng (červen 2020), „Vylepšené hranice pro slunečnicové lemma“, Sborník z 52. výročního sympozia ACM SIGACT o teorii práce s počítačem, Association for Computing Machinery, s. 624–630, arXiv:1908.08483, doi:10.1145/3357713.3384234, ISBN 978-1-4503-6979-4
- Deza, M.; Frankl, P. (1981), „Každá velká sada vektorů ve stejné vzdálenosti (0, + 1, –1) tvoří slunečnice“, Combinatorica, 1 (3): 225–231, doi:10.1007 / BF02579328, ISSN 0209-9683, PAN 0637827
- Erdős, Paul; Rado, R. (1960), „Křižovatkové věty pro systémy množin“, Journal of the London Mathematical Society, Druhá série, 35 (1): 85–90, doi:10.1112 / jlms / s1-35.1.85, ISSN 0024-6107, PAN 0111692
- Jech, Thomas (2003), Teorie množinSpringer
- Kunen, Kenneth (1980), Teorie množin: Úvod do důkazů o nezávislosti, Severní Holandsko, ISBN 978-0-444-85401-8
- Shanin, N. A. (1946), „Věta z obecné teorie množin“, C. R. (Doklady) Acad. Sci. URSS (N.S.), 53: 399–400
- Tao, Terence (2020), Lemma slunečnice prostřednictvím Shannonovy entropie Co je nového (osobní blog)
Poznámky
- ^ Původní termín pro tento koncept byl „-systém ". Nověji termín" slunečnice ", případně zavedený Deza & Frankl (1981), ji postupně nahrazoval.
- ^ „Časopis Quanta - osvětlovací věda“. Časopis Quanta. Citováno 2019-11-10.