Co łączy mapę dróg, internet i drzewo genealogiczne? Wszystkie w maksymalnym uproszczeniu są zbiorem połączonych ze sobą elementów, który określamy grafem. W jaki sposób matematyka może opisywać jego strukturę? Badaniem tego obszaru zajmie się prof. Michał Pilipczuk z Wydziału Matematyki, Informatyki i Mechaniki UW, który na realizację projektu WYDRA otrzymał grant Consolidator Europejskiej Rady ds. Badań Naukowych. To już drugi grant ERC w jego dorobku.

Pierwszy był BOBR. W 2020 roku prof. Michał Pilipczuk – wówczas siedem lat po doktoracie – otrzymał swój pierwszy grant (Starting) Europejskiej Rady ds. Badań Naukowych (European Research Council, ERC). W projekcie badał strukturalne oraz dekompozycyjne własności sieci i wykorzystał je do stworzenia szybkich metod obliczeniowych rozwiązujących trudne problemy.

Temat sieci pojawia się też w projekcie WYDRA, na którego realizację 9 grudnia badacz otrzymał grant Consolidator.

– WYDRA dotyczy grafów. To podstawowe obiekty matematyczne modelujące wszelkiego rodzaju sieci. Grafy występujące w zastosowaniach często mają określoną strukturę – mówi prof. Pilipczuk. I wskazuje przykłady: sieci drogowe są „płaskie”, a społecznościowe składają się z gęstych klastrów i rzadszych połączeń między nimi.

Matematyka z informatyką

Od dawna wiadomo, że badania nad algorytmami grafowymi i matematyczną teorią ich struktury wzajemnie się przenikają i dopełniają. Jeśli chodzi o tzw. grafy rzadkie (czyli takie, w których liczba połączeń między elementami jest stosunkowo niewielka), można je analizować z wykorzystaniem dobrze rozwiniętego zestawu narzędzi i metod. Zupełnie inaczej jest w przypadku badań grafów gęstych (z wieloma krawędziami) – wiedza na ich temat pozostaje niepełna. Prof. Michał Pilipczuk postanowił wziąć ten problem na warsztat.

– Chcemy stworzyć spójną i solidną teorię opisującą strukturę grafów gęstych – mówi naukowiec, dodając, że jego zamiarem jest połączenie trzech głównych podejść w tym zakresie:

• logicznego, w którym graf traktowany jest jako zestaw powiązanych obiektów, a do jego opisu używa się narzędzi zaczerpniętych z logiki matematycznej i teorii modeli;
• algebraicznego, znanego jako teoria minorów wierzchołkowych. W tym ujęciu badanie grafu opiera się na analizie właściwości jego macierzy sąsiedztwa (dużych tabel opisujących połączenia) za pomocą metod algebry liniowej nad ciałem binarnym (najprostszym możliwym ciałem matematycznym);
• „zgrubnego”, rozpatrującego graf jako pewną przestrzeń metryczną. To podejście pozwala badać ogólną strukturę grafu w dużej skali, bez wchodzenia w szczegóły dostrzegane tylko lokalnie.

– W opisywaniu struktury w grafach myślimy zazwyczaj poprzez różnego rodzaju dekompozycje. Widzimy np. dwa klastry w wielkiej sieci, rozłączamy je i dostrzegamy, że między nimi jest niewiele połączeń, co pozwala nam je „rozwiązać” osobno. Do tego potrzebny jest nam język matematyki, czyli strukturalna teoria grafów zajmująca się dowodzeniem twierdzeń o dekompozycjach sieci – mówi prof. Pilipczuk i dodaje: – Spodziewamy się, że wyniki naszych badań otworzą drogę do wielu nowych zastosowań – zarówno w kombinatoryce, jak i w projektowaniu algorytmów. Mamy nadzieję, że wskaże to też interesujące kierunki dalszych badań na styku teorii grafów i informatyki teoretycznej.

W przygotowaniu aplikacji projektowych o granty ERC naukowców z UW wspiera Biuro Międzynarodowych Programów Badawczych, które organizuje spotkania informacyjne i szkoleniowe, panele próbne przed drugim (ustnym) etapem konkursu, prowadzi konsultacje indywidualne, a w razie przyznania środków na realizację projektu, przygotowuje umowę grantową.

BMPB UW współpracuje z ekspertem ds. prezentacji naukowych – prof. Piotrem Wasylczykiem z Wydziału Fizyki, panelistami ERC i laureatami grantów ERC (recenzje wewnętrzne, panele próbne) oraz z KPK PB UE (NCBR).