doc. Mgr. Robert Šámal, Ph.D.

Držitel Neuron Impulsu 2011

matematika

Když v 18. století řešil švýcarský matematik Leonard Euler úlohu, jak projít sedm mostů v městě Královci pouze jednou tak, aby se vrátil zpět do výchozího místa, byla teorie grafů pouze zábavnou hříčkou. Dnes je jednou z významných disciplín aplikované matematiky. Robert Šámal se věnuje jednoznačnosti vektorového barvení grafů. Jeho výsledky vedly k řešení jiných matematických problémů a budou mít nečekané důsledky na zdánlivě nesouvisející disciplíny.

Neuron Stories – poslechněte si příběhy českých vědců


Na teorii grafů lze formalizovat jak problémy z nejrůznějších vědních oborů, tak praktického života. Grafy totiž dobře slouží jako abstrakce nejrůznějších problémů. Teorie grafů zkoumá vlastnosti těch grafů, které reprezentují množiny objektů, u kterých chceme znázornit, že jsou některé prvky propojeny. Už od 50. let 20. století je tato teorie disciplínou s četnými aplikacemi – kdysi se jednalo o mapy železničních sítích, dnes grafy popisují například strukturu webových stránek. Po propojení teorie grafů a lineárního programování navíc došlo ke zkoumání nových veličin, např. barevnosti.

Robert Šámal se ve svém výzkumu věnuje tzv. semidefinitnímu programování (zobecnění lineárního programování), takže vrcholům grafu nepřiřazuje čísla, ale mnoharozměrné vektory. K jakým závěrům došel? Podařilo se mu vyřešit variantu Hedetniemiho součinové hypotézy a dokázat Sabidussiho větu pro dvě varianty vektorového barvení, což byl problém, který na své řešení čekal desítky let. Své poznatky aplikoval na zkoumání silně regulárních grafů, a objevil tak zajímavý koncept – jednoznačné vektorové barvení.

Skutečnost, že existuje právě jedno řešení, bude mít nečekané důsledky, a poznatky Roberta Šámala povedou k řešení dalších, dlouho otevřených, problémů.

Když matematik udělá „úkrok stranou“ – rozhovor s Robertem Šámalem 

Zabýváte se teorií grafů. Jak se poznatky z této oblasti matematiky uplatňují v praktickém životě?
Teorie grafů se využívá například při plánování elektrické, silniční nebo železniční sítě, s cílem propojit co nejvíce obcí a zároveň spotřebovat co nejméně stavebního materiálu. Dalším příkladem je sestavování rozvrhu přednášek na vysoké škole, tak aby učitel nemusel být ve stejnou hodinu ve dvou posluchárnách. Podobný problém vzniká při využívání počítačové paměti, kdy se rozhoduje, které informace už lze vymazat a jaké ještě uchovat. Ovšem v rámci finančního Impulsu od Neuronu jsem nezkoumal grafy, ve kterých se jednotlivé body označují barvami. Zabývám se tzv. vektorovou barevností, kdy jsou barvy nahrazeny vektory – šipkami. Jde o klasický matematický „úkrok stranou“, kdy hledáme problém, který je původnímu dostatečně podobný, aby se dal vhodně použít, ale zároveň je jednodušší, a tedy efektivněji řešitelný počítačovým algoritmem.

Jako držitel Neuron Impulsu jste dostal jeden milion korun. Jak jste peníze využil?
Díky této částce se mi podařilo navázat spolupráci s Davidem E. Robersonem a s dalšími odborníky z různých světových institucí. Mohl jsem více jezdit na konference a také panu Robersonovi financovat návštěvu Prahy, při které jsme pokračovali v předchozí spolupráci započaté po e-mailu a na konferencích.

Jaké výsledky vyplynuly z vašeho společného výzkumu?
Pokud jde o odborné výsledky, podařilo se vyřešit variantu Hedetniemiho součinové hypotézy pro dvě varianty vektorové barevnosti. Dále zkoumáme otázku jednoznačnosti vektorového barvení a její aplikace. To má nečekané důsledky mj. pro zkoumání různých variant symetrií grafů. Naše poznatky jsme popsali v několika článcích. Za nejdůležitější pokládám text, jehož autory jsou kromě mě Chris Godsil, David E. Roberson a Simone Severini. Článek přijali do časopisu Combinatorica. Další výsledky, které připravujeme, budou také publikovány v předních časopisech v oboru, což často, ale ne vždy, koresponduje s vysokým impakt faktorem.

doc. Mgr. Robert Šámal, Ph.D.

V roce 2001 absolvoval Matematicko-fyzikální fakultu UK v Praze. Titul Ph.D. v oboru počítačových věd obhájil na své alma mater v roce 2006. Od této doby pracoval dva roky jako postdoktorand na Simon Fraser University v Kanadě. Od roku 2008 je zaměstnán v oddělení aplikované matematiky MFF UK. Během svého výzkumu, který financoval Nadační fond Neuron, se ve spolupráci s matematikem Davidem E. Robersonem věnoval jednoznačnosti vektorového barvení grafů. A jeho výsledky budou mít dalekosáhlé důsledky na nečekané disciplíny a na řešení jiných dlouho otevřených matematických problémů.