Mykhaylo Tyomkyn

Lecture on Probabilistic techniques (NTIN022) 2023/24

List of topics covered by lectures is at the bottom of this webpage.

Exams

Anotation

Organization remark

Lecture notes

Syllabus

References

• [AS] N. Alon, J. Spencer: The Probabilistic Method, J. Wiley and Sons 1993, 2008, 2015.
• [MU] M. Mitzenmacher, E. Upfal: Probability and Computing: Randomized Algorithms and Probabilistic Analysis, Cambridge University Press, 2005.
• [MR] R. Motwani, P. Raghavan: Randomized algorithms, Cambridge University Press, 1995.
• [O'D] R. O'Donell: Probability and Computing lecture notes
• J. Spencer: Ten lectures on the probabilistic method, SIAM, 1987
• One chapter of J. Matoušek, J. Nešetřil: Invitation to Discrete Mathematics. (covers just a first part of the class).

Topics covered

Oct 3

Introduction. A proof that $R(k,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. Further applications of the basic probabilistic method: 2-colourable hypergraphs, Sperner's theorem, Erdős-Ko-Rado theorem. [MV 1, 2, AS 1]

Oct 10

Applying expectation of the random variable: Tournaments with many Hamiltonian paths; MAXCUT - existence of a cut in a graph with many edges (with derandomization); balancing vectors - $\pm$ sums of unit vectors can be achieved both high and low (with derandomization); large sum-free subsets. Alterations: weak Turán theorem; an improved lower bound on $R(k,k)$. [MV 3, 4.1, AS 1.4, 2.1, 2.2, 2.4, 3.1, 3.2]

Oct 17

Existence of graphs of large girth and chromatic number. An application of alterations in combinatorial geometry: the Heilbronn triangle problem.
(non-examinable:) Existense of dense triple systems with no $k+2$ vertices inducing $k$ or more edges. [MV 4.2, AS 3.3, your own notes for the last part]

Oct 24

The second moment method: variance of a random variable, standard deviation, covariance. Variance of a sum of random variables. Chebyshev's inequality. Lower bound for the middle binomial coefficient. Threshold functions - triangle counts in G(n,p). The threshold function for containment of a balanced graph $H$. [MV 5.1, 5.2, 5.3, AS 4]

Oct 31

More on the second moment method: the clique number of $G(n,1/2)$. A randomized algorithm for computing the median [MV 5.4, MU 3.4]

Nov 7

Lovász local lemma: statement and proof. The symmetric version. General implies symmetric. Applications: an improved lower bound on $R(k,k)$, 2-colourable hypergraphs revisited. [MV 6.1, 6.2, AS 5.1, 5.2, 5.3]

Nov 14

Applications of the Lovász local lemma: existence of injective functins (joke), cycles of length divisible by $k$ in directed graphs, colourings of the reals: colourful translates. A sketch of an application of an asymmetric version: a lower bound on the Ramsey numbers R(3,k). [MV 6.3, 6.4, 6.5, AS 5.2, 5.3]

Nov 21

Basic Chernoff's bound. Applications: max degree in $G(n,1/2)$, combinatorial discrepancy. A more general variant of Chernoff's bound. [MV 7.1, 7.2]

Nov 28

Application of Chernoff to randomized rounding for the k-matching problem. The anti-concentration counterpart to Chernoff, and an application: a lower bound on discrepancy of set systems. [MV 7.2, 7.3]

Dec 5

Markov chains: definition, representation by digraphs and by matrices. Symmetric random walks, Gambler's ruin. Algorithms for 2-SAT and for 3-SAT (will be finished next time). [MU 7.1]

Dec 12

Finishing 2-SAT and 3-SAT algorithms. More Markov chains: accesible/communicating states, states transient/recurrent, and null/positive recurrent. Periodic/aperiodic states/MC. Ergodic states/MC. Theorem about stationary distribution of a Markov chain (statement) [MU 7.1, 7.2, 7.3]

Dec 19

Theorem about stationary distribution of a Markov chain: proof based on these notes by Prof Sgall. Balls and bins: birthday paradox, maximum load. [MU 7.3, 5.1, 5.2]

Jan 9

Balls and bins: the Poisson approximation. A lower bound on max load. [MU 5.3, 5.4]