Seznam probrané látky najdete na konci teto stranky (průběžně doplňováno).
Rozsah výuky: ZS 2/2 Z, Zk
Oct 7 How to prove existence of a graph by tossing a coin: $R(k) > 2^{k/2}$, where $R(k,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. Overview of basic notions in probability: probability space, union bound, independent events.
Oct 14 Another application of basic probabilistic method: a formula in CNF, where every clause has $k$ literals and number of clauses is less than $2^k$ is satisfiable. Continuing in the Overview of basic probability: random variables, linearity of expectation, distribution, independent variables. List of distributions, both discrete and continuous:
Two application of linearity of expectation: The expected number of fixed points in a random permutation. Tournaments with many Hamiltonian paths. (Method of indicator variables.)
Oct 21
MAX-SAT -- how to satisfy many clauses in a formula.
Given a graph with $m$ edges, there is a cut of the graph with at least $m/2$ edges.
Plus a method to derandomize this proof -- find an algorithm, that really finds the cut.
Method of alterations
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$.
Markov's inequality
The existence of graphs with arbitrarily large girth and chromatic number.
Nov 4
Bayes law.
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. Application to an estimate of the middle binomial coefficient.
Nov 11
Probability that $G(n,p)$ has some monotone graph property (e.g., containing a triangle)
is (for a fixed $n$) a nondecreasing function of $p$.
Proof: coupling.
Treshold functions. The treshold function for property that
$G(n,p)$ contains a triangle is $\frac1n$ (a proof using Chebyshev inequality).
The treshold function for property that $G(n,p)$ contains a fixed subgraph $H$ is $n^{-1/\rho}$ where $\rho$ is
the maximal density of a subgraph of $H$.
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.)
(Note about Khintchin's inequality.)
Nov 18 Lovász local lemma: motivation, definitions, statement of the three versions. Two easy applications: satifiability of a "sparse" $k$-SAT formula and selecting disjoint paths. Proof of the basic version.
Nov 25 Chernoff bounds: Definitions, statement. Connections to the binomial distribution and central limit theorem. Easy application: amplification of the error probability for randomized algorithms (BPP languages). Application: Routing in hypercube networks. [MU 4.5.1, also MR 4.2 with the combinatorial lemma for the bound on delay]
Dec 2 Chernoff bounds: Proofs of the binomial version (uniformly random $-1,+1$ variables) and the multiplicative version. Comparison of the bounds. Estimating an unknown mean. [MU 4.1-4.3]
Dec 9 Balls and bins: Routing in hypercubes (continued). Balls and bins model, statement of the bounds, proof of the lower bound. [MU 5.1-5.2]
Dec 16 Balls and bins: Poisson approximation, upper bound proof for balls and bins. The power of two choices: statement without proofs. [MU 5.4, 14.1]
Jan 5 Markov chains: definition, Markov (memoryless) property, time-homogeneous discrete Markov chains. Applications: 2-SAT algorithm, 3-SAT randomized algorithm in time $O(1.334^n)$. Classification of states: transient, positive recurrent, null recurrent. [MU 7.1-7.2]
Jan 12 Markov chains: Example: Gambler's ruin. Classification of chains: irreducible, (a)periodic, ergodic. Stationary distribution, its existence and uniqueness for finite ergodic chains. Notes on the stationary distribution. Continuous time Markov processes, exponential distribution: definitions, relation between them. [MU 7.3, 8.3, 8.5]