Zanurzenia metryczne

Prowadzący

Marcin Kotowski

marcin.kotowski1@gmail.com

Opis

Wyobraźmy sobie, że mamy mapę Warszawy wyposażoną w czasy dojazdu. Chcemy narysować te mapę uwzględniając owe czasy (krótszy dojazd = krótsza odległość na mapie). Czy da się to zrobić bez zniekształceń, skoro odległość "czas dojazdu" jest zazwyczaj różna od fizycznej odległości dwóch punktów?

Powyższy problem stanowi przykład problemu z teorii zanurzeń metrycznych. Mamy abstrakcyjny zbiór, w którym mierzymy odległości w jakiś sposób (możemy np. myśleć o grafie z odległością równą najkrótszej ścieżce między wierzchołkami), i chcemy narysować go w przestrzeni euklidesowej tak, by zachować odległości. Czy zawsze da się to zrobić? A jeśli nie, to jakie są przykłady "trudnych" grafów o bardzo "nieeuklidesowej" geometrii?

Teoria zanurzeń metrycznych posiada wiele zastosowań algorytmicznych. Zanurzenie grafu w "ładniejszą" przestrzeń często pozwala projektować wydajne algorytmy - aby rozwiązać problem grafowy, zanurzamy go w przestrzeń, której struktura pozwala na dobry algorytym, dbając o to, by odległości nie uległy zbytniemu zniekształceniu.

Zanurzenia metryczne stanowią bogaty dział z przecięcia matematyki i informatyki teoretycznej (zahaczający o teorię grup, grafy losowe, spektralną teorię grafów, …). Na zajęciach postaram się zaprezentować wstęp do podstawowych zagadnień i konstrukcji, zostawiająć jak najwięcej pracy do wykonania Wam. 1. dzień poświęcimy na wstęp i proste zadanie, 2. na dowodzenie twierdzeń w małych grupach, 3. na tzw. "desery".

Program zajęć

(ulegnie jeszcze uzupełnieniu)
Poniżej zamieszczam zrzut tematów wokół których będą się obracać zajęcia - materiał omówiony na zajęciach będzie stanowił ścisły podzbiór poniższego:

• podstawowe zanurzenia; jak pokazać, że nie da się czegoś dobrze zanurzyć
• uniwersalne zanurzenia w przestrzeń euklidesową: jak dobrze zanurzyć przestrzeń metryczną nie wiedząc nic o jej strukturze
• zanurzenia konkretnych grafów: drzewa, "trudne" grafy
• zanurzenia w losowe drzewa i zastosowania algorytmiczne
• jak zanurzenia metryczne pomagaj szukach rzadkich cięć w grafach

Wymagania

• elementarny rachunek prawdopodobieństwa
• pojęcie przestrzeni metrycznej
• brak oporów przed przyswajaniem pewnej ilości nowej teorii

Ww. elementy zostaną wprowadzone i przetestowane w zadaniach kwalifikacyjnych.

Zadania kwalifikacyjne

Dostępne tutaj: Zadania kwalifikacyjne W razie pytań etc., śmiało piszcie na maila!

Uwaga: zadanie 6. okazało się trudne, zastąpiłem je zadaniem 7.