Přednáška Pravděpodobnostní metoda 2 (NTIN095)

Probabilistic method 2 (NTIN095)

Jiří Sgall a Robert Šámal


Rozsah výuky: ZS 2/2 Z, Zk

Organizační poznámky, organization

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.

Covered topics

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.

Textbook

Plánovaná témata, planned topics

V této přednášce se budeme zabývat pokročilejšími pasážemi jako: