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