Aktuální číslo:

2024/5

Téma měsíce:

Čas

Obálka čísla

3,9995

 |  2. 5. 2023
 |  Vesmír 102, 247, 2023/5

Narozeninový problém je dosti známá úloha z kombinatoriky. Ve dvacátých letech minulého století ji obecně matematicky formuloval F. P. Ramsay (1903–1930). Pro nás může být nastíněn takto: Jaký je nejmenší počet hostů R(k), které chceme pozvat na večírek, abychom zaručili, že se mezi nimi vyskytne skupina k hostů, kteří se již předtím znali, nebo skupina k hostů, z níž se předtím nikdo s nikým neznal (pro jistotu dodávám v rámci té skupiny). Pro případ k = 3 nejmenší počet hostů, který to zajistí, je šest. To si můžete ověřit i bez matematiky hrubou silou tak, že si všechny možnosti jednu po druhé vypíšete. Obecně dosud úlohu nikdo nevyřešil. Geniální Paul Erdös našel spolu s G. Szekeresem v r. 1935 alespoň omezení shora, že totiž počet hostů 4k zaručuje, že se mezi nimi vyskytne skupina k hostů, kteří se již předtím znali, nebo skupina k hostů, z níž se předtím nikdo s nikým neznal. To nebylo moc uspokojivé, protože toto číslo je pro větší hodnoty k příliš veliké. A tak se nedivme, že po více než 90 letech neúspěšných pokusů o snížení Erdösovy horní hranice, vzbudila velkou pozornost práce čtyř matematiků, v níž snížili omezení shora na R(k) = 3,9995k. Jejich práce je dostupná na arxiv.org/abs/2303.09521. Rozdíl nám může připadat směšně malý, ale pro velká k je významný. Nejde o společenskou kuriozitu – práce má význam pro grafy s prvky náhodnosti, které mají aplikace v reálných problémech.

P. Ball: Nature, 2023, DOI: 10.1038/d41586-023-00840-5

Ke stažení

OBORY A KLÍČOVÁ SLOVA: Matematika
RUBRIKA: Mozaika

O autorovi

Ivan Boháček

Mgr. Ivan Boháček (*1946) absolvoval Matematicko-fyzikální fakultu UK v Praze. Do roku 1977 se zabýval v Ústavu fyzikální chemie J. Heyrovského molekulovou spektroskopií, do roku 1985 detektory ionizujících částic v pevné fázi v Ústavu pro výzkum, výrobu a využití radioizotopů. Spolu s Z. Pincem a F. Běhounkem je autorem knihy o fyzice a fyzicích Newton by se divil (Albatros, Praha 1975), a se Z. Pincem pak napsali ještě knihu o chemii Elixíry života a smrti (Albatros, Praha 1976). Ve Vesmíru působí od r. 1985.
Boháček Ivan

Doporučujeme

Divocí kopytníci pečují o krajinu

Divocí kopytníci pečují o krajinu

Josef Matyáš  |  6. 5. 2024
Zubr, pratur a divoký kůň dokážou výborně udržovat rozsáhlé plochy krajiny. Vyplývá to z aktualizovaného dokumentu Metodika přirozené pastvy...
Relativistický čas – čas našeho světa

Relativistický čas – čas našeho světa

Pavel Krtouš  |  6. 5. 2024
„Někteří filozofové … se domnívají, že fyzika není schopna popsat nejzákladnější aspekty reality, a zavrhují ji proto jako zavádějící formu...
Čas na poslední kafe

Čas na poslední kafe uzamčeno

Tomáš Knedlík  |  6. 5. 2024
Kávu zbožňujeme pro její vůni a chuť, ale také pro její povzbuzující účinky. Omamná vůně kávy se uvolňuje při pražení, kdy vznikají těkavé...