Rozsah výuky: ZS 2/2 Z, Zk
Cvičení probíhá hlavně formou individuální práce posluchačů (domácí úkoly, třeba řešit průběžně během semestru).
This course is given in English. It includes regular homeworks and recitation sections.
October 12 [JS]. Correlation inequalities. Four functions theorem in distributive lattices. Set systems, Kleitman's lemma.
October 19 [JS]. FKG inequality. Monotone properties. Extensions of partial orderings.
October 26 [JS]. Discrepancy. Beck-Fiala theorem. Beck's conjecture on three permutations.
November 2 [JS]. Entropy. Entropy method for bounding the discrepancy.
November 9 [JS]. Linear discrepancy. Janson inequality, statement and application to estimate the probability that a random graph is triangle-free.
November 16 [JS]. Janson inequality, proof. Clique number of a random graph, two-value concentration.
November 23 [RS]. Conditional expectation, martingales. Azuma inequality.
November 30 [RS]. Filtration, Doob's martingale. Edge-exposure and vertex-exposure martingale. Lipschitz condition implies boundedness of martingale differences. Easy application: concentration of chromatic number (Shamir, Spencer).
December 7 [RS]. Applications of martingales: concentration of number of points avoided by a random mapping, of the norm of a random +-1 sum of given vectors, isoperimetric inequality, 4-point concentration of chromatic number.
December 14 [RS]. One more application of martingales: chromatic number of G(n,1/2). Talagrand inequality -- introduction.
December 21 [RS]. Plan: Talagrand inequality -- proof and a simple application.
January 4 [RS]. Talagrand inequality -- applications.
January 11 [RS]. "Multistep applications of prob.method": 1) bound for choosability for graphs of high minimal degree. 2) A glimpse over the proof of n/log n bound for chromatic number of graphs without 3- and 4-cycles.