# 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

• N. Alon, J. Spencer: The Probabilistic Method, 3rd edition, J. Wiley and Sons 2008

### Plánovaná témata, planned topics

V této přednášce se budeme zabývat pokročilejšími pasážemi jako:
• Korelační nerovnosti
• Martingaly a pokročilé odhady Černovova typu
• Pseudonáhodnost
• Fázové přechody v náhodných grafech
• Diskrepance
• Testování grafových vlastností
• náhodné regulární grafy
• konstrukce objektů několikastupňovou náhodnou volbou (Rödl nibble) -- kupř. v aplikaci na Johanssonův odhad \$O(D/log D)\$ na barevnost grafů s max. stupněm D a bez trojúhelníků a čtyřcyklů
• algoritmické lokální lemma