Testowanie własności w czasie stałym

Wyobraźmy sobie, że dostajemy bardzo duży graf (mający np. \(10^{15}\) wierzchołków) i mamy orzec, czy spełnia jakąś własność - jest dwudzielny, planarny (da się narysować na płaszczyźnie bez przecięć), nie zawiera trójkątów, zawiera klikę ustalonego rozmiaru etc. [1] Ze względu na rozmiar grafu czas działania algorytmu powinien być podliniowy (np. dla \(n\) wierzchołków działać w czasie\(\sqrt{n}\)), a najlepiej w ogóle - stały! (niezależny od rozmiaru grafu).

W takiej wersji zagadnienie jest oczywiście nie do rozwiązania. Załóżmy więc dodatkowo, że dopuszczamy użycie losowości - możemy np. zapytać się, jak wygląda otoczenie losowo wybranego wierzchołka. Chcemy, by odpowiedź była poprawna z prawdopodobieństwem 0.99. Co więcej, mamy obiecane, że wejściowy graf albo spełnia żądaną własność, albo jest daleki od jej spełniania - np. żeby uczynić go dwudzielnym, trzeba by zmodyfikować 1/10 wszystkich możliwych krawędzi. Okazuje się, że przy takich założeniach wiele własności grafowych jest testowalnych - to znaczy, dopuszczają algorytm działający w czasie stałym! (na przykład wystarczy do tego 1000 zapytań o krawędzie, niezależnie od tego, jak duży jest graf)

Na zajęciach wprowadzimy podstawowe pojęcia i metody dotyczące testowania własności grafowych:

• które własności są testowalne, a które nie?
• jak może wyglądać algorytm efektywnie testujący własność grafową?
• jak pokazać, że jakaś własność nie jest testowalna w czasie stałym?
• które grafy są "trudne", a które "łatwe"? jaki to ma zwiazek z geometrią grafu?
• jak dużo informacji o globalnej strukturze grafu niesie jego lokalna struktura (np. otoczenie losowo wybranego wierzchołka)?

Okazuje się, że pytania te szybko prowadzą do ciekawej i nietrywialnej kombinatoryki grafowej (tw. Szemerediego o regularności) i zahaczają o inne rejony matematyki, np. żywo rozwijającą się teorię granic grafów (graph limits). W trakcie zajęć zarysujemy przypadek grafów gęstych (mających rzędu n^2 wierzchołków) i być może wspomnimy o zagadnieniach związanych z grafami rzadkimi (mającymi liniowo wiele krawędzi) - błądzenia losowe, ekspandery etc.

Wymagania

Znajomość podstawowych pojeć z teorii grafów i elementarnego rachunku prawdopodobieństwa, obycie z notacją asymptotyczną i może jakaś bardzo, bardzo postawowa ogłada algorytmiczna - będzie sprawdzona w zadaniach kwalifikacyjnych.