The probabilistic method is a very powerful technique commonly used in combinatorics and computer science. Its essence is the following: In order to establish the existence of a combinatorial structure with certain properties, one constructs an appropriate probability space and shows that a randomly chosen element of this space possesses the desired properties with positive probability.

The course will provide an introduction to the probabilistic method. We will present some of the most widely used methods and tools and illustrate them with applications to `real-life' combinatorial problems.

Among topics that will be covered in the class are the following: linearity of expectation, the second moment method, the Lovász local lemma, correlation inequalities, martingales, large deviation inequalities.

The students enrolling in the course are expected to have working knowledge of basic notions in graph theory and be familiar with basic concepts of discrete probability.

N. Alon and J.H. Spencer, The Probabilistic Method, Wiley, 2016 (4th edition)

March 4

What is the probabilistic method?; asymptotic notation; lower bounds for diagonal Ramsey numbers; 2-colourability of uniform hypergraphs; probabilistic proofs of three classical results in extremal set theory: Sperner's theorem, Bollobás's cross-intersecting set pairs inequality, and the Erdős–Ko–Rado theorem

March 11

Linearity of expectation; large sum-free subsets of a set of integers; large cuts in graphs; (un)balancing unit vectors; large independent sets in graphs with a given degree sequence (the theorem of Caro and Wei); derivation of Turán's theorem; the crossing lemma of Ajtai–Chvátal–Newborn–Szemerédi

March 18

The 'supersaturation' theorem of Erdős and Simonovits; large independent sets in triangle-free graphs (the theorem of Ajtai–Komlós–Szemerédi); Ramsey numbers revisited; improved lower bound on the minimum number of edges in a non-2-colourable uniform hypergraph; Chebyshev's inequality and the second moment method

March 25

Sets with distinct sums; Turán's proof of the Hardy–Ramanujan theorem; Weierstrass's approximation theorem; Hoeffding's inequality; upper bounds on discrepancy of hypergraphs with large uniformity; the symmetric version of the Local Lemma; 2-colourability of uniform hypergraphs with small maximum degree

April 1

Lower bounds on Ramsey numbers via the Local Lemma; the Local Lemma; derivation of the symmetric version of the Local Lemma from the general one; Latin transversals

April 8

Decomposable coverings of ℝ

^{3} by unit balls; algorithmic version of the Local Lemma; nonrepetitive sequences via the "entropy compression" method; Harris's inequality; distributive lattices

April 29

The Fortuin–Kasteleyn–Ginibre (FKG) inequality; the Ahlswede–Daykin inequality ("four functions theorem"); the XYZ theorem; Janson's inequality

May 6

Proof of Janson's inequality; estimating the probability that G(n,p) is triangle-free; when does every vertex of G(n,p) lie in a triangle?; lower tail estimates via Janson's inequality; martingales

May 13

Azuma's inequality; concentration of the chromatic number of G(n,p); McDiarmid's inequality; vertex isoperimetry in the hypercube; Talagrand's convex distance; Talagrand's inequality

May 20

Large deviation inequalities for certifiable Lipshitz functions; self-information and entropy; estimates for sums of binomial coefficients; Brègman's theorem; Shearer's inequality

May 27

Triangle-intersecting families of graphs; the largest number of cliques in a graph with a given number of edges; edge-isoperimetry in the hypercube; the maximum number of independent sets in a regular bipartite graph (Kahn's theorem); the hard-core model; derivation of Kahn's and Shearer's theorems from bounds on the occupancy fraction (Davies–Jenssen–Perkins–Roberts)

June 3

Bounding the occupancy fraction in the hard-core model on triangle-free graphs; dependent random choice; Turán numbers for bipartite graphs; Ramsey numbers of bipartite graphs with bounded degree

June 10

Randomised algebraic construction of large K

_{s,t}-free graphs