Trójstronny projekt ,,Struktura produktowa grafów planarnych" będzie prowadzony przez trzy zespoły pod kierownictwem Gwenaëla Joreta z Wolnego Uniwersytetu w Brukseli, Torstena Ueckerdta z Karlsruher Institut für Technologie, oraz Piotra Micka z Uniwersytetu Jagiellońskiego. Budżet przyznany polskiemu zespołowi to ponad 900 tys. zł.
Badania w projekcie mieszczą się w teorii grafów, czyli dziedzinie poświęconej matematyce sieci. Naukowcy będą badać grafy planarne, tj. grafy które mogą być narysowane bez przecięć na kartce papieru. Jednym z najbardziej znanych twierdzeń w matematyce jest Twierdzenie o Czterech Barwach: każdy graf planarny można poprawnie pokolorować czterema kolorami. Dowód tak niewinnego twierdzenia wymaga głębokiego zrozumienia struktury grafów planarnych i jest jednym z głównych osiągnięć matematyki i informatyki teoretycznej XX wieku.
Grafy planarne to klasyczny temat badań i czasami można odnieść wrażenie, że wszystko co ważne o strukturze grafów planarnych zostało już odkryte i dogłębnie zrozumiane. Nic bardziej mylnego, wciąż pojawiają się zaskakujące twierdzenia. Jeden z takich wyników został uzyskany przez trójkę liderów tego projektu w 2019 r. i to twierdzenie zostało ochrzczone twierdzeniem o strukturze produktowej. Twierdzenie mówi, że każdy graf planarny można zanurzyć w produkt dwóch prostych grafów: grafu podobnego do drzewa oraz ścieżki. Okazało się, że takie zanurzenie jest kluczem do rozwiązania wielu otwartych od lat problemów kombinatorycznych i algorytmicznych. Celem tego projektu jest poszukiwanie nowych zastosowań twierdzenia o strukturze produktowej oraz budowanie teorii wokół tego twierdzenia.
Serdecznie gratulujemy!
