Matematyk z AGH: Poszukuję piękna w grafach

Dr Marcin Stawiski z Wydziału Matematyki Stosowanej opowiada o swoich badaniach nad kolorowaniem grafów, kategoriach estetycznych w matematyce oraz sposobie myślenia cechującym adeptów królowej nauk, który wyróżnia ich na tle reprezentantów innych dziedzin wiedzy.

Piotr Włodarczyk (Centrum Komunikacji i Marketingu AGH): Zajmuje się pan stosunkowo od niedawna eksplorowanym przez matematyków obszarem teorii grafów, mianowicie kolorowaniem rozróżniającym.

Dr Marcin Stawiski: Ten problem nie jest aż tak nowy, ponieważ pierwsza praca autorstwa Babaia na ten temat pojawiła się już w 1977 roku. Jednak nie odbiła się ona szerokim echem w środowisku matematycznym i w pewnym sensie została na długi czas „zapomniana”. Dopiero w 1996 roku kolorowania rozróżniające zostały niezależnie wprowadzone przez Alberstona i Collins i przeszły do matematycznego mainstreamu.

Jak na matematykę, to jednak niedługa historia.

Faktycznie, jest dużo starszych problemów. Ten jednak do najnowszych nie należy. Ukazało się też już kilkaset prac na ten temat.

Powiedzmy sobie, co jest istotą tego problemu.

Zacznijmy od tego, czym jest graf. Jest to obiekt składający się z punktów zwanych wierzchołkami, gdzie każda para takich punktów może być połączona ze sobą krawędzią lub nie. Kolorowanie grafu to po prostu przyporządkowanie wierzchołkom lub krawędziom odpowiedniego koloru, czyli inaczej pewnej etykiety, którą nazywamy kolorem. W przypadku kolorowania rozróżniającego chcemy, żeby graf został pokolorowany w taki sposób, że każda symetria daje w wyniku inne kolorowanie. Rozważa się zarówno wersję kolorowania rozróżniającego, gdzie dwa połączone ze sobą wierzchołki mogą mieć te same kolory, jak i taką, gdzie nie mogą mieć tego samego koloru – jak ma to miejsce w przypadku kolorowania właściwego.

Co stanowi tutaj trudność?

W przypadku kolorowania grafów – nie tylko rozróżniającego, ale również innego typu – chodzi zwykle o dobranie najmniejszej możliwej liczby kolorów potrzebnej do pokolorowania danego grafu w określony sposób. Musimy wówczas udowodnić dwie rzeczy: po pierwsze, że nie da się pokolorować rozróżniająco jeszcze mniejszą liczbą kolorów, a po drugie, że zawsze można pokolorować rozróżniająco przy użyciu liczby kolorów, którą wskazaliśmy.

Proszę opisać, jak przebiega taki proces.

Jeśli mówimy o problemie ogólnego kolorowania grafów, wybieramy zawsze jakąś ich daną klasę, czyli zbiór grafów posiadający określone własności – może to mieć na przykład związek z ich liczbą wierzchołków czy krawędzi. Zwykle chcemy też, aby taka klasa była jak najszersza – wówczas staramy się jak najbardziej zmniejszyć liczbę kolorów niezbędną do danego kolorowania dla tego szerokiego zakresu grafów, albo zajmujemy się węższą klasą, ale próbujemy znaleźć dalej idące ograniczenia niż jest to możliwe w przypadku szerszych klas. Dowody, które bezpośrednio przeprowadzamy, czasami przybierają formę algorytmu dla danego kolorowania, albo jedynie pokazują, że dane kolorowanie jest możliwe, ale bez wskazywania, jak miałoby wyglądać.

W przypadku algorytmów, często istotny jest też praktyczny aspekt ich zastosowania – chodzi nie tylko o to, żeby można było pokolorować dany graf w określony sposób, ale też zrobić to szybko przy użyciu komputera. Często uzyskanie optymalnego kolorowania, które udałoby się przeprowadzić w akceptowalnym czasie, jest bardzo trudne. Dlatego wykorzystuje się tzw. algorytmy aproksymacyjne, które co prawda nie zawsze pozwalają na przeprowadzenie kolorowania najmniejszą możliwą liczbą kolorów, ale umożliwiają zrobić to szybko.

Jakie klasy grafów pana szczególnie interesują?

W większości moich prac zajmuję się grafami nieskończonymi – czyli takimi, które mają nieskończoną liczbę wierzchołków. Istotne jest dla mnie to, czy dana klasa grafów jest ciekawa. Można rozpatrywać to pod względem praktycznym – czyli możliwości ich zastosowania w matematyce, ale też w innych dziedzinach – albo estetycznym.

Estetycznym?

Chodzi o pewnego rodzaju piękno, które każdy matematyk rozumie nieco inaczej. Może ono tkwić zarówno w uzyskanym wyniku, jak również w rozumowaniu, które do niego doprowadziło.

A czym jest ono dla pana?

Dla mnie jest to uzyskanie najbardziej optymalnych wyników dla ciekawych klas grafów. Piękno objawia się właśnie w dowodach, a także w tym, czy do uzyskania danego wyniku użyliśmy metod, które nie zostały użyte nigdy wcześniej – czasami taka metoda jest przydatna jedynie w celu przeprowadzenia jednego konkretnego dowodu, a innym razem może okazać się przydatna również w przypadku rozwiązywania innych problemów.

Co pańskie dotychczasowe rozważania wniosły do tej dziedziny?

Współpracowałem z dr. Florianem Lehnerem z Uniwersytetu w Auckland (Nowa Zelandia), prof. Wilfriedem Imrichem z Uniwersytetu w Graz (Austria), dr. Trevorem Wilsonem z Uniwersytetu w Miami (USA) oraz matematykami z AGH: dr. Jakubem Kwaśnym, dr hab. Moniką Pilśniak, prof. AGH i dr. hab. Rafałem Kalinowskim, prof. AGH. Razem z Moniką Pilśniak udało mi się pokazać optymalne ograniczenie dla liczby użytych kolorów w kolorowaniu rozróżniającym krawędziowym dla grafów nieskończonych ze względu na maksymalny stopień wierzchołków, czyli liczbę innych wierzchołków, z którymi dany wierzchołek jest połączony. Podobne ograniczenie, również optymalne, udało mi się uzyskać wraz z Moniką Pilśniak oraz Florianem Lehnerem dla kolorowań wierzchołkowych. Razem z Florianem Lehnerem, Jakubem Kwaśnym, Moniką Pilśniak oraz Trevorem Wilsonem pracowałem nad kolorowaniami krawędziowymi grafów regularnych, to znaczy takich, w których każdy wierzchołek ma ten sam stopień. Finalnie udało nam się uzyskać optymalne ograniczenie zarówno dla grafów skończonych, jak i nieskończonych.

Natomiast ostatnio zainteresowałem się kolorowaniami listowymi, którymi zajmuję się wspólnie z Jakubem Kwaśnym. Są to takie typy kolorowania, w których każdy wierzchołek lub krawędź ma przyporządkowaną pewną listę możliwych kolorów i może być pokolorowany jedynie kolorami z własnej listy. Właściwie każdy typ kolorowania może być przeprowadzony również w takiej wersji.

Jak dziś wygląda praca matematyka? To bardziej praca z komputerem, czy raczej z kartką i długopisem?

Większość mojej pracy odbywa się w głowie. Dopiero, gdy udaje mi się wpaść na bardziej konkretny zarys rozumowania, przenoszę go na papier czy do komputera. Trochę inaczej wygląda to, kiedy współpracuję z innymi matematykami – wtedy przeważnie dyskutujemy i wykorzystujemy tablicę.

Co przyciągnęło pana na uniwersytet?

Zainteresowałem się matematyką już w szkole podstawowej. Duży wkład miał w to mój brat, który uświadomił mi, jak ważna i ciekawa jest to dziedzina wiedzy. Przez pewien czas interesowałem się równocześnie fizyką i chemią, ale na studia wybrałem matematykę na AGH i nigdy tej decyzji nie żałowałem. Na studiach magisterskich zajmowałem się matematyką w finansach i ubezpieczeniach – wtedy najbardziej interesowały mnie rachunek prawdopodobieństwa i statystyka, z której pisałem pracę magisterską. Dopiero na ostatnim roku zdecydowałem, że chcę zajmować się teorią grafów. Dostrzegałem, że wiąże się z nią wciąż sporo ciekawych, nierozwiązanych problemów, którymi mógłbym się zająć. Tej decyzji również nie żałuję.

Jak zachęcił by pan innych do studiowania matematyki?

Przede wszystkim, studiowanie matematyki rozwija pewien szczególny, analityczny i formalny sposób myślenia, który nie jest aż tak bardzo podkreślany na innych studiach, na przykład inżynierskich.

Co ma pan na myśli, mówiąc o formalnym sposobie myślenia? Czy matematyk nie może być wolny w swoich rozważaniach?

Matematyk musi być dokładny. Niedokładność w rozumowaniu nie jest w tym przypadku możliwa, jak ma to często miejsce w innych dziedzinach nauki.

Myślałem, że jedynie humaniści mogą bujać z głową w chmurach.

Myli się pan. Nawet fizycy teoretyczni używają często metod, których nie można uznać wprost za matematyczne. Wśród matematyków zostałyby one uznane za niedopuszczalne.