Dr hab. Piotr Micek, prof. UJ z Wydziału Matematyki i Informatyki Uniwersytetu Jagiellońskiego zrealizuje międzynarodowy, trójstronny projekt badawczy dzięki finansowaniu w konkursie Weave-UNISONO. Naukowcy z Krakowa, Brukseli i Karlsruher będą prowadzić badania grafów planarnych, które mogą być narysowane bez przecięć na kartce papieru.
Konkurs Weave-UNISONO to efekt wielostronnej współpracy między instytucjami finansującymi badania naukowe, skupionymi w stowarzyszeniu Science Europe. Został ogłoszony w celu uproszczenia procedur składania i selekcji projektów badawczych we wszystkich dyscyplinach nauki, angażujących badaczy z dwóch lub trzech krajów europejskich. Wyłanianie laureatów opiera się na procedurze agencji wiodącej, w myśl której tylko jedna z instytucji partnerskich odpowiedzialna jest za pełną ocenę merytoryczną wniosku, pozostali partnerzy akceptują wyniki tej oceny.
W ramach programu Weave partnerskie zespoły badawcze składają wnioski o finansowanie równolegle do agencji wiodącej oraz do właściwych dla siebie instytucji uczestniczących w programie. Wspólny projekt musi zawierać spójne plany badań, wyraźnie ukazujące wartość dodaną współpracy międzynarodowej.
Projekt, którego kierownikiem jest dr hab. Piotr Micek, prof. UJ z Instytut Informatyki Analitycznej UJ, dotyczy teorii grafów, czyli dziedziny nauki poświęconej matematyce sieci. Badania będą realizowane we współpracy z prof. Gwenaëlem Joretem z Wolnego Uniwersytetu Brukselskiego oraz prof. Torstenem Ueckerdem z niemieckiego Instytutu Technicznego w Karlsruher. Budżet przyznany polskiemu zespołowi to ponad 900 tys. zł.
”W tym projekcie będziemy 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żemy 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” - czytamy w opisie planowanych badań.
Obecnie 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ł uzyskanych przez trójkę liderów tego projektu w 2019 roku 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 aplikacji twierdzenia o strukturze produktowej oraz budowanie teorii wokół tego twierdzenia.
Drugi trójstronny projekt zakwalifikowany do finansowania w konkursie Weave-UNISONO zrealizują uczeni z Uniwersytetu im. Adama Mickiewicza w Poznaniu we współpracy z Wolnym Uniwersytetem Brukselskim oraz Uniwersytetem Johanna Wolfganga Goethego we Frankfurcie nad Menem.
