Powrót

Zaawansowane zagadnienia kombinatoryki (2017/2018)

Wykład odbywa się w piątki w godz. 9:15 - 11:00 w sali 1.30/C-13.
Przeznaczony jest dla studentów studiów drugiego stopnia Informatyki WPPT PWr.

Literatura

  1. A. Frieze, M. Karoński, Introduction to Random Graphs
  2. W. Lipski, W. Marek, Analiza kombinatoryczna, PWN, 1986

Zaliczenie kursu

Na ostatnich ćwiczeniach odbędzie się kolokwium stanowiące podstawę oceny końcowej. Ostateczna ocena uwzględniać będzie także aktywność na ćwiczeniach.
Kolokwium składać się będzie z części teoretycznej (łatwej), w której trzeba będzie wysłowić najważniejsze definicje i twierdzenia oraz dwóch zadań podobnych do zadań z list (jedno z grafów losowych, drugie z twierdzeń podziałowych). Dodatkowo będzie też zadanie trudniejsze (umożliwiające otrzymanie oceny 5,5).

Zrealizowany materiał

  1. Przestrzenie probabilistyczne
    1. Skończona i przeliczalna przestrzeń probabilistyczna
    2. Definicja ogólna
    3. $\sigma$-ciało zbiorów borelowskich, zbiorów mierzalnych
    4. Produkty przestrzeni probabilistycznych
  2. Grafy losowe
    1. Model $G(n,p)$
    2. Model $G_{n,m}$
    3. Model $G(\mathbb{N},p)$
    4. Charakteryzacja (nieskończonego) grafu losowego
    5. Zależność pomiędzy $P_{G(n,p)}(\mathcal{P})$ oraz $P_{G_{n,m}}(\mathcal{P})$ dla dowolnej własności $\mathcal{P}$
    6. Przestrzeń $G(n,p)$ jako $G(n,p_1)\times G(n,p_2)$ dla $1-p=(1-p_1)(1-p_2)$
    7. Analogiczny fakt dla $G_{n,m}$
    8. Własności monotoniczne: rosnące, malejące
    9. Zależność pomiędzy $P_{G(n,p)}(\mathcal{P})$ oraz $P_{G_{n,m}}(\mathcal{P})$ dla monotonicznej rosnącej własności $\mathcal{P}$
    10. Próg (threshold) dla monotonicznej własności $\mathcal{P}$
    11. Próg istnieje!
    12. Nierówności Markowa i Czebyszewa oraz ich warianty dla zmiennych lisowych o wartościach naturalnych
    13. Dla $\mathcal{P}=\{\emptyset\}$ w modelu $G(n,p)$ próg wynosi $p^*=\frac{1}{n^2}$
    14. Ostry próg
    15. Nierówność $P(X>0)\ge\displaystyle\frac{(EX)^2}{EX^2}$ dla zmiennej losowej o wartościach naturalnych
    16. Ostry próg dla własności "istnieje wierzchołek izolowany" wynosi $m^*=\displaystyle\frac{1}{2}n\ln{n}$
    17. Ewolucja grafu $G_{n,m}$
      1. Gdy $m<< n$, to $\lim_{n\to\infty}P_{G_{n,m}}(Las)=1$
      2. Gdy $m<<\sqrt{n}$, to $\lim_{n\to\infty}P_{G_{n,m}}(\mathcal{K})=1$, gdzie $\mathcal{K}$ oznacza brak wierzchołków stopnia 2
      3. Gdy $m>>\sqrt{n}$, to $\lim_{n\to\infty}P_{G_{n,m}}(\mathcal{K})=0$
      4. $m^*=\sqrt{n}$ jest progiem dla własności $\mathcal{K}$
      5. Twierdzenia Cayleya: liczba drzew o wierzchołkach $[n]$ to $n^{n-2}$
      6. Zależność rekurencyjna
      7. Dowód elementarny
      9. Kody Prufnera
      10. Gdy $m<< n^{\frac{k-2}{k-1}}$, to $\lim_{n\to\infty}P_{G_{n,m}}(\mathcal{T}_k)=1$, gdzie $\mathcal{T}_k$ oznacza brak podgrafów, które są drzewami o $k$ wierzchołkach
      11. Gdy $m>>n^{\frac{k-2}{k-1}}$, to $\lim_{n\to\infty}P_{G_{n,m}}(\mathcal{T}_k)=0$, a nawet więcej :)
      12. $m^*=n^{\frac{k-2}{k-1}}$ jest progiem dla własności $\mathcal{T}_k$
  3. Teoria Ramsey'a
    1. Twierdzenie Ramsey'a - równoważne sformułowania i analiza łatwych przypadków
    2. Liczby Ramsey'a $R_r(q_1,q_2,\ldots,q_t)$
    3. Dowód twierdzenia Ramsey'a
    4. Dowód dla $r=2$ używający drzew
    5. $R_2(q_1,q_2,\ldots,q_t)\le \displaystyle\frac{t^{\sum_{k=1}^t q_k-2t+1}-1}{t-1}+1$
    6. Analiza przypadku nieskończonego
    7. Oszacowania górne na liczby Ramsey'a $R_2(m,n)$ wynikające z poprzednich dowodów
      1. $R_2(m,n)\le 2^{m+n-3}$
      2. $R_2(m,n)\le {m+n-2 \choose m-1}$
      3. Porównanie asymptotycznego zachowania tych oszacowań dla $n=m$
    8. Rodziny dwukolorowalne
    9. Moc rodziny dwukolorowalnej $\mathcal A\subseteq [X]^n$ wynosi co najmniej $2^{n-1}$
    10. Dolne ograniczenie na liczby Ramsey'a $R_2(n,n)\ge \frac{n}{e\sqrt{2}}2^{n/2}(1+o(1))$
    11. Twierdzenie van der Waerdena
    12. Ideał van der Waerdena, ideał gęstości zero, twierdzenie Szemerediego
    13. Zbiory wolne od sum
    14. Twierdzenie Schura
    15. Ograniczenie dolne na liczby Schura
    16. Związek liczb Schura z liczbami Ramsey'a: $S(n)\le R_2(\underbrace{3,3,\ldots,3}_n)-1$
    17. Oszacowania dla liczb $R_2(\underbrace{3,3,\ldots,3}_n)$

Powrót