Prestižní Nerodova cena za průkopnickou práci v teorii grafů
Jaroslav Nešetřil a Patrice Ossona de Mendez položili základy významné oblasti strukturní teorie grafů, známé jako „sparsity“ (česky „řídkost“). Jejich práce významně ovlivnila nejen čistou matematiku, ale má i praktické aplikace v algoritmické teorii grafů, složitosti algoritmů a matematické logice. Letos byli oceněni Nerodovou cenou.
Minulou středu byla udělena prestižní Nerodova cena za rok 2025, která je důkazem mimořádného přínosu pro oblast teoretické informatiky. Tuto cenu, kterou každoročně uděluje Evropská asociace pro teoretickou informatiku (EATCS), obdrželi profesor Jaroslav Nešetřil z Informatického ústavu UK (IUUK) a profesor Patrice Ossona de Mendez z École des hautes études en sciences sociales (EHESS) a IUUK za své průkopnické práce o takzvané „řídkosti“ (sparsity) v teorii grafů. Oba vědci cenu převzali osobně v polské Varšavě.
Nerodova cena se uděluje za výjimečné práce v oblasti víceproměnných algoritmů a je pojmenována po významném americkém matematikovi a logikovi Anilu Nerodovi. Oceňuje trvalý přínos, který posunul hranice oboru. Ocenění se uděluje za jednu nebo sérii prací publikovaných v posledních 15 letech a jeho laureáty vybírá komise složená z předních odborníků.
Letošní cena byla udělena za zásadní příspěvek, který položil základy „sparsity“ – oblasti strukturální teorie grafů, jež se zaměřuje na pojmy „nikde hustých“ tříd grafů a tříd grafů s omezenou expanzí. Tyto dvě definice pevně zachycují koncept lokální, strukturální řídkosti grafů a konečných struktur. Ve své oceňované sérii článků i ve své monografii Sparsity vydané v roce 2012 nakladatelstvím Springer zavedli Nešetřil a Ossona de Mendez klíčové pojmy a ukázali jejich fundamentální povahu. Podařilo se jim dokázat širokou škálu vlastností a ekvivalentních charakterizací, čímž vytvořili mocný soubor technik pro práci s řídkými grafy a strukturami.
Jak již ukázaly jejich předchozí práce, tento soubor nástrojů lze použít k navrhování parametrizovaných algoritmů pro problémy lokální povahy. Během let to vedlo k několika přelomovým výsledkům v parametrizované složitosti, zejména k velkým pokrokům v pochopení složitosti problémů definovatelných v logice prvního řádu.
Průkopnické dílo Nešetřila a Ossony de Mendeze propojilo strukturální teorii grafů s logikou a víceproměnnou algoritmikou, a zanechalo tak trvalou stopu ve všech těchto oborech. Práce obou vědců byla podpořena grantem Synergy Evropské výzkumné rady (ERC).
