Zanurzenia metryczne

Prowadzący

Marcin Kotowski
moc.liamg|1ikswotok.nicram#moc.liamg|1ikswotok.nicram

Opis

laakso.png

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.

O ile nie zaznaczono inaczej, treść tej strony objęta jest licencją Creative Commons Attribution-ShareAlike 3.0 License