3,9995

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ů 4^k 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,9995^k. 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