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
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ů).
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.