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, 2008 (3rd edition)
S. Janson, T. Łuczak, and A. Ruciński, Random Graphs, Wiley, 2000
October 26
What is the probabilistic method?; asymptotic notation; diagonal Ramsey numbers; winning sets in tournaments; 2-colorability of uniform hypergraphs; sum-free sets; disjoint pairs in families of sets
November 2
Intersecting families and the Erdős–Ko–Rado theorem; linearity of expectation; fixed points in a random permutation; large cuts in graphs; monochromatic cliques in 2-colorings of K
n; permanents and Minc's conjecture / Brègman's theorem; Hamiltonian paths in tournaments
November 9
Balancing vectors; alterations method; Ramsey numbers revisited; large independent sets in graphs and the theorems of Turán and Caro and Wei; graphs with large girth and chromatic number; improved lower bound on the minimum number of edges in a non-2-colorable n-uniform hypergraph
November 16
Chebyshev's inequality and the second moment method; sets with distinct sums; Turán's proof of the Hardy–Ramanujan theorem; graph properties and threshold functions; threshold for appearance of a fixed balanced graph as a subgraph
November 23
The Local Lemma: symmetric, general, and lopsided versions; 2-colorability of locally sparse uniform hypegraphs; lower bounds for Ramsey numbers via the Local Lemma; multicolored sets of real numbers; Latin transversals
November 30
Algorithmic version of the Local Lemma; Nonrepetitive sequences via the "entropy compression" method; dependent random choice; Turán numbers for bipartite graphs; Ramsey numbers for hypercubes
December 7
Embedding bipartite graphs with bounded degree in dense graphs (using dependent random choice); Ahlswede–Daykin inequality / "four functions theorem"; Fortuin–Kasteleyn–Ginibre (FKG) inequality and its special cases: Harris inequality and Kleitman's lemma
December 14
The XYZ theorem; Chernoff bounds; martingales; Azuma's inequality; concentration of the chromatic number of G(n,p)
December 28
The chromatic number of G(n,1/2); four-point concentration of the chromatic number of G(n,p); sums of vectors in normed spaces; independent bounded differences inequality; isoperimetric inequalites in product spaces; Talagrand's inequality
January 4
More on Talagrand's inequality; longest increasing subsequence in a random permutation; Janson's inequality; clique number of G(n,1/2) via Janson's inequality; triangles in G(n,c/n)
January 11
Bonferroni inequalities and Brun's sieve; when does every vertex of G(n,p) lie in a triangle?; large deviation inequalities for sums of mostly independent indicator random variables; lower bounds for the off-diagonal Ramsey numbers R(l,k)
January 18
Large deviation inequalities for sums of mostly independent indicator random variables (ctd); the number of triangles containing a vertex in G(n,p); self-information and entropy; estimates for sums of binomial coefficients; Shearer's lemma; Loomis–Whitney inequality; triangle-intersecting families of graphs
January 25
Proof of Shearer's lemma; the maximum number of independent sets in a regular graph: Kahn's entropy proof and Zhao's reduction; lower bound on the crossing number of a graph; the Szemerédi–Trotter theorem; Elekes' lower bound on the numbers of distinct sums and products