Opis zajęć
Przez graf losowy $G(n,p)$ rozumiemy nie jeden konkretny obiekt, jak ma to miejsce w przypadku grafu prostego, ale całą przestrzeń możliwych jego realizacji — grafów prostych na $n$ wierzchołkach. Ściśle rzecz biorąc jest to przestrzeń probabilistyczna $(\Omega,2^\Omega,P)$, gdzie $\Omega$ jest zbiorem wszystkich grafów prostych na $n$ wierzchołkach, a $P(\omega) = p^k(1-p)^{n-k}$, dla $\omega\in\Omega$ o $k$ krawędziach. Będzie nas przede wszystkim interesowała ewolucja grafu losowego, czyli co się dzieje, gdy $n\to\infty$, a $p = p(n)$. Pokażemy, jak za pomocą języka pierwszego rzędu formalizować różne grafowe własności, np. cykliczność. Dla tego szczególnego słownika udowodnimy też twierdzenie Fagina, wykorzystując Restaurację Alicji i wnioski z twierdzenie Gödla o pełności.
Program
- Trochę logiki, kombinatoryki i prawdopodobieństwa
- Grafy losowe i inni
- Ewolucja grafu losowego
- Funkcja przejścia
- Prawo "0-1" i tw. Fagina
- Gry strukturalne Ehrenfeuchta
Wymagania
- Rozróżnianie nieskończoności przeliczalnej i nieprzeliczalnej
- Obycie z relacjami binarnymi
- Podstawowe sposoby zliczania struktur kombinatorycznych
- Umiejętność prowadzenia dowodów indukcyjnych
Literatura
Być może coś się uda polecić.
Kwalifikacja
- rozwiązania proszę wysyłać na adres: mwrochna na gmail.com (format - tex/pdf, bo to dobry pretekst, żeby poćwiczyć; ale może też być skan/zdjęcie lub tekst z krzakami)
- oczekujemy, że ostatecznie każdy zrobi wszystkie zadania, ale jeśli
- utknąłeś w zadaniu? nie wiesz nawet do końca o co chodzi w treści? pytaj! (ewentualnie poszukaj na en.wikipedia). Chodzi tylko o to by rozumieć podstawy przed warsztatami.
- w razie jakichkolwiek problemów, uwag itd. - napisz!
- nudzi ci się? spróbuj zadanka off-topic.
1. Jakie jest prawdopodobieństwo, że w n rzutach symetryczną monetą dostaniemy dokładnie 6 reszek?
2. Jakie jest prawdopodobieństwo, że w n rzutach symetryczną kostką dostaniemy dokładnie 6 szóstek? Do czego będzie ono zbiegać dla dużych n (króciutko uzasadnij)?
3. ${n\choose 0}+{n\choose 1}+{n\choose 2}+\cdots+{n\choose n}$ =?, udowodnij indukcyjnie.
4. ${n\choose 0}^2+{n\choose 1}^2+{n\choose 2}^2+\cdots+{n\choose n}^2$ =?, udowodnij.
5. Rozpatrzmy grafy o n wierzchołkach, zorientowane, pełne. (Między każdymi dwoma różnymi wierzchołkami mają krawędź albo w jedną albo w drugą stronę.)
Ograniczmy się do tych, w których dla każdej krawędzi $u\to v$ zachodzi $d_{out}(u)>d_{out}(v)$. (liczba krawędzi wychodzących z u jest większa niż z v).
Udowodnij, że wszystkie takie grafy są izomorficzne. (Czyli "z dokładnością do izomorfizmu istnieje tylko jeden taki graf".)