Robert Šámal, Martin Tancer

Přednáška Pravděpodobnostní metoda (NTIN022) 2014/15

Probabilistic method (NTIN022) 2014/15


The class is scheduled Wed 12:20 in S5. The exercises are based on home assignments, with an irregularly scheduled exercise session, which will happen on Wed 14:00. Questions for home assignments can be found on web page of the TA.

Přednáška se koná ve středu od 12:20 v S5. K přednášce jsou také cvičení. Cvičení je založeno na samostatném řešení příkladů. Jednou za 2-3 týdny bude cvičení "prezenční", kde se budou ukazovat řešení a další komentáře, to se bude konat ve středu ve 14:00.

List of covered topics at the end of this page. (English version of the page under construction, contact the lecturer if anything is unclear.)

Seznam probrané látky najdete na konci teto stranky.


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

Zkoušky/Exams

If you know when do you like to pass the exam, send an email to both lectures: samal@iuuk and tancer@kam, where `iuuk' stands for iuuk.mff.cuni.cz and `kam' stands for kam.mff.cuni.cz

Z probrané látky -- teorie i její aplikace na jednodušší příklady. Zkoušku je též možné získat za hvězdnou účast na cvičení (velký počet vyřešených domácích úkolů).

Anotace

Pravděpodobnostní metoda je způsob důkazu existence kombinatorických objektů "počítáním". Pro mnoho důležitých objektů je to jediný známý důkaz. Pravděpodobnostní metoda se stále častěji objevuje i v návrhu a analýze algoritmu a v dalších odvětvích informatiky a patří k nejdůležitějším nástrojům diskrétní matematiky.
O náplní přednášky si můžete udělat lepší představu podle látky probrané minule.

Organizační poznámky

Cvičení probíhá hlavně formou individuální práce posluchačů (domácí úkoly, třeba řešit průběžně během semestru).

Učební text

Skripta J. Matoušek, J. Vondrák: The probabilistic method vyšla v ITI Sériích (preprintova řada Institutu teoretické informatiky MFF UK) pod číslem 2002-087 a je k dispozici v informatické knihovně MFF UK.
Elektronická verze v postscriptu zkomprimovaném programem "gzip" (2 malé stránky na jednu stranu A4, celkem asi 90 malých stran) zde.

Osnova

Základní pravděpodobnostní metoda, linearita střední hodnoty, metoda modifikace, použití variance. Lovászovo lokální lemma. Pseudonahodnost a explicitní konstrukce. Odhady Černovova typu. Ilustrace metod na příkladech z různých oblasti diskrétní matematiky a informatiky.

Další literatura

Probraná látka

Oct 8 How to prove existence of a graph by tossing a coin: $R(k) > 2^{k/2}$, where $R(k)$ is the Ramsey number, the minimal number of vertices that guarantees that a graph has an independent set or a clique with $k$ vertices. (Proof works for $ \ge 3$, we only showed it works for $k$ large enough.) Overview of basic notions in probability: probability space, union bound, independent events, random variables, linearity of expectation.

Oct 15 Let $m(k)$ be the minimal number of edges of a $k$-uniform hypergraph that is not 2-colorable. We proved that $m(k) \ge 2^{k-1}$ and that $m(3)=7$. Finishing overview of probability: indpendent random variables. Useful estimates: bounds for $1-x$ (from above and below), for factorials and for the binomial coefficients. For reference, consult the lecture notes or the following list of useful estimates. Note, though, that there's much more in the list, than you will ever need!

Oct 22 The Erdős-Ko-Rado Theorem. Linearity of expectation, Indicator functions. The expected number of fixed points in a random permutation. Tournaments with many Hamiltonian paths. Given a graph with $m$ edges, there is a cut of the graph with at least $m/2$ edges. Weak Turán's theorem: $\alpha(G) \geq n/2d$ where $\alpha$ is the independence number of a graph with $n$ edges and average degree $d$.

Oct 29 Markov's inequality. The existence of graphs with arbitrarily large girth and chromatic number. Given $n$ unit vectors, they can be equipped with signs $-1$ or $1$ such that the norm of their sum (with respect to the signs) is at most $\sqrt n$. (At least $\sqrt n$ can be reached as well.) Bollobás's Theorem and $\tau$-critical families of sets.

Nov 5 Probabilistic proof of the existence of a set of $n$ points in the square such that the area of each triangle formed by these $n$ points has area at least $\frac 1{100n^2}$. The second moment method: variance, covariance, variance of a sum of random variables, Chebyshev inequality.

Nov 19 Estimating the middle binomial coefficient: $\binom{2m}{m} \ge 2^{2m}/(4\sqrt m + 2)$. Treshold functions. The treshold function for property that $G(n,p)$ contains a triangle is $\frac1n$. The treshold function for property that $G(n,p)$ contains a fixed subgraph $H$ is $n^{-1/\rho}$ where $\rho$ is the density of $H$, provided that $H$ does not contain a subgraph with density bigger then $\rho$. (The proof partly unfinished.)

Nov 26 Finishing the proof from the last time. Estimating the expected clique number of the random graph $G(n, 1/2)$. It is assymptotically almost surely below $2 \log_2 n$ but above any function $k(n)$ satisfying $\lim_{n\to\infty}\binom{n}{k(n)}2^{-\binom{k(n)}2} = \infty$. (The proof partly unfinished.)

Dec 3 Finishing the proof from the last time. New topic: Lovász local lemma: motivation, definitions, statement of the symmetric version. Two easy applications: 2-coloring a hypergraph and finding an injective mapping.

Dec 10 Application of Lovász local lemma to find directed cycles in a digraph. Proof of LLL. General version (with hints how to prove it). Coloring reals: statements and preliminary thoughts about the proof.

Dec 17 Coloring reals using LLL and compactness (only the countable case). Concentration of sum of independent 0/1 variables. Motivation by application for max.degree of the random graph $G(n,1/2)$ and the proof.

Jan 7 Two applications of Concentration of sum of independent 0/1 variables: discrepancy of set system and randomized rounding of a solution to a linear relaxation of computationally hard problems. (The second one requires more general, nonsymmetric version.) Comments about connection to the Central Limit theorem.