Przejdź do głównej treści

Widok zawartości stron Widok zawartości stron

Wiadomości

Nawigacja okruszkowa Nawigacja okruszkowa

Widok zawartości stron Widok zawartości stron

Grant na polsko-niemiecko-walońskie badania nad grafami planarnymi

Grant na polsko-niemiecko-walońskie badania nad grafami planarnymi

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.

Polecamy również
Jeszcze więcej grantów NCN dla badaczy z UJ

Jeszcze więcej grantów NCN dla badaczy z UJ

Naukowcy UJ otrzymają ponad 73 mln zł na realizację badań podstawowych

Naukowcy UJ otrzymają ponad 73 mln zł na realizację badań podstawowych

Studenci WMiI UJ triumfatorami konkursu im. Józefa Marcinkiewicza

Studenci WMiI UJ triumfatorami konkursu im. Józefa Marcinkiewicza

Badacze UJ wśród pierwszych laureatów konkursu MINIATURA 8

Badacze UJ wśród pierwszych laureatów konkursu MINIATURA 8

Widok zawartości stron Widok zawartości stron