Informace: Od 25.11.
přednáší J. Matoušek. Termíny
zkoušek: na stránce prof. Matouska, mé na SISu.
1.
přednáška 7.10.2004. Organizační
pokyny a literatura. Obecně o pravděpodobnostní metodě.
"Problém" s pravděpodobnostní metodou: Dokázali
jsme třeba, že (náhodný) graf G má vlastnost V s pravděpodobností > 0.3. Ale vždyť přece chceme dokázat existenci
grafu s vlastností V s úplnou jistotou a
nestačí nám jen vědět, že možná existuje a
možná ne?? Jak je to??
Opakování
pojmů teorie pravděpodobnosti: pravděpodobnostní prostor, jevy,
nezávislost jevů, podmíněná pravděpodobnost,
náhodná veličina, střední hodnota,
nezávislé náhodné veličiny.
P[A1 U A2 U ... U Ak] <= P[A1]
+ P[A2] + ... + P[Ak].
Pro dvě nezávislé náh. veličiny X a Y platí E[XY] = E[X]E[Y].
Věta: Pro Ramseyovo číslo R(k,k) platí odhad R(k,k) > 2k/2 -1.
2. přednáška
14.10.2004. Důkaz horního
odhadu R(k,k)
<= 22k -1-1 pomocí stromového
argumentu. Opakování užitečných odhadů pro
faktoriál a binomické koeficienty. Číslo m(k): nejmenší počet hran k-grafu, který není
řádně 2-obarvitelný.
Odhad m(k) >= 2k-1
pomocí pravd. metody. Určení
hodnoty m(3)=7,
dokončení příště.
3.
přednáška 21.10.2004. Dokončení
důkazu odhadu m(3) >= 7. Dva v pravd. metodě často
(mlčky) užívané argumenty. 1. Rozkladový:
rozkládají-li jevy B1,
..., Bk pravd. prostor a A je jev, potom P[A | Bi]
<= a pro každé i implikuje P[A] <= a (totéž platí s <
, >= , > a =). 2. Zmenšovací:
Máme-li dva pravd.
prostory U a V s rovnoměrnými
rozděleními P a Q,
zobrazení F z U do V splňující |F
-1(y)| = const (pro y probíhající V, speciálně
je F surjekce) a
jevy A v U a B ve V splňující A = F -1(B), potom P[A] =Q[B]. Použití obou
argumentů v důkazu Erdos-Ko-Radoovy věty o
protínajících množinových systémech
(na n-prvkové množině
je nanejvýš B(n - 1, k - 1) k-prvkových podmnožin,
které se po dvou protínají). Bollobásova věta (jsou-li A1 , ... ,
An k-prvkové množiny a B1 , ... , Bn l-prvkové
množiny takové, že průnik Ai s Bj je prázdný, právě když i = j, potom počet n je nejvýše B(k + l, k) = B(k + l, l)) a
její aplikace pro transverzálově kritické k-uniformní množinové
systémy.
28.10.2004 přednáška odpadla pro
státní svátek.
4.
přednáška 4.11.2004. (přednáška
ve znamení trojice) Tři aplikace Bollobásovy věty. 1.
Odhad počtu antipodálních dvojic vrcholů v grafu (počtu
dvojic vrcholů xi , yi
takových, že deg(xi) <= a, deg(yi) <= b a xi , yj mají pro i = j
vzdálenost alespoň 3 a pro i
různé od j nejvýše
2). 2. Odhad velikosti indukovaného
párování v Kneserově grafu K(n, k). 3. Odhad počtu po dvou
sousedících simplexů v Rd . Linearita
střední hodnoty a tři aplikace. 1. Průměrný počet
pevných bodu permutace (tři přístupy: (i) naivní,
(ii) rozkladem na indikátorové náhodné
veličiny a linearitou střední hodnoty a (iii) pomocí
Burnsideova lemmatu). 2. Existuje turnaj na n vrcholech, který má
alespoň n! / 2n-1 hamiltonovských
cest. 3. Každý graf s m hranami
má bipartitní podgraf s alespoň m / 2 hranami.
5.
přednáška 11.11.2004. Metoda
alterace ve dvou aplikacích. 1. Zlepšení odhadu R(k, k) > (k/21/2e).(1+ O(1/k)).2k/2 pro
Ramseyova čísla z primitivního použití linearity
stř. hodnoty na odhad R(k, k) > (k/e).(1+ O(1/k)).2k/2 . 2. Erdosova věta o existenci grafů s velkým obvodem
a velkou barevností. Metoda druhého momentu, nejprve
definice: rozptyl, směrodatná odchylka, kovariance. Čebyševova
nerovnost. Linearita rozptylu za předpokladu nezávislosti
sčítanců. Odhad B(2m, m) > 22m
/ (4m1/2 + 2) pomocí Čebyševovy nerovnosti, důkaz příště.
6.
přednáška 18.11.2004. Důkaz
odhadu binom. koeficientu. Čebyševova nerovnost v
problému z kombinatorické teorie čísel: Nechť f(n) je maximální k takové, že existuje k přirozených čísel
x1, x2,
..., xk z množiny {1,
2, ..., n} s vlastností, že všech 2k jimi určených
sum je vzájemně různých. Z triviální
nerovnosti 2 f(n) <n.f(n) se
dostane f(n) < log2n
+ log2log2 n+ O(1) a Čebyšev dá f(n) < log2n
+ (1/2).log2log2 n+ O(1). Lemma: Var[ Xn ] / E[Xn ]2 -> 0 implikuje, že P[ Xn
> 0 ] -> 1. Prahová funkce pro monotonní
grafové vlastnosti. Věta: Vlastnost
"obsahovat H jako podgraf"
má pro vyvážený graf H s hustotou h prahovou funkci n-1/h.
leden 2005