Math 585
Probablistic methods in combinatorics

Instructor:   Jozsef   Balogh
Office: 233B Illini Hall
Phone: (217) 244-1918 (office)
E-mail: jobal@math.uiuc.edu
Time and place: 11 pm- 11:50am MWF, 347 Altgeld Hall

MIDTERM: Time and place: 10:10 am- 2:00 pm May 7, 347 Altgeld Hall

MAKE UP CLASSES: Time and place: 6 pm- 7:30 pm April 23, 447 Altgeld Hall

Jan 21 (W): sections 1.1, 1.2, 1.3 is covered.
Jan 23 (F): sections 1.4, 2.2, 2.4 is covered
Jan 30 (F): sections 2.5, 3.1, 3.2 is covered + Caro - Wei proof of Turan's thm
Feb 2 (M): n points in units quare without small triangle; high girth and chroomatic number graphs; 2-colorings of n-uniform hypergraphs (Pluhar proof)
Feb 4 (W): Chebyshev Inequality, basics of the second moment method (chapter 4)
Feb 6 (F): Disjoint pairs (1.5), Number of different prime divisors (4.2)
Feb 9 (M): EKR proof, K_4 in random graph (4.4)
Feb 11 (W): H in random graph, clique number of G(n,1/2)
Feb 18 (W): Rodl nibble (state), covering; state and prove Local Lemma.
Feb 20 (F): Applications of Local Lemma, Ramsey numbers and hypergraph coloring.
Feb 23 (M): Applications of Local Lemma: unit balls, multicolored subsets of R, partitioning into linear forests.
Feb 25 (W): Local Action Lemma (by Anton Bernsteyn).
Feb 27 (F): Local Action Lemma (by Anton Bernsteyn).
March 2 (M): Applications of Local Lemma: Cycles in directed graphs, Latin Transversals.
March 4 (W): Correlation Inequalities: 4-function theorem.
March 6 (F): Correlation Inequalities: FKG-inequality, Kleitman's lemma.
March 9 (M): Correlation Inequalities: XYZ inequality, Weierstrass Theorem.
March 11 (W):Chernoff bound, Janson's inequality
March 13 (F):Janson's inequality, Brun's Sieve.
March 16 (M): Number of triangles containing a vertex in G(n,p)
March 18 (W): Number of ways writing a sum, pseudo random tournaments (Ch 9)
March 30 (M): Quasi random graphs (9.3)
April 1 (W): Quasi random graphs, expanders (9.2)
April 3 (F): Expander Mixing lemma (Alon-Chung), proof of EKR thm
April 6 (M): Erdos-Selfridge, Dependent random choice lemma.
April 8 (W): Dependent random choice lemma: Ramsey-Turan, introduction to martingales.
April 10 (F): Martingales and random walk.
April 13 (M): Chromatic number of G(n,1/2).
April 15 (W): Chromatic number of G(n,p), Sections 7.4, 7.5.
April 17 (F): Tallagrand's Inequality.
April 22 (W): Kim-Vu polynomial, crossing lemma
April 24 (F): Szemeredi-Trotter + applications (number of unit distances, sum-products).
April 27 (M): Discrepancy and entropy
April 29 (W): Discrepancy and Beck-Fiala Thm
May 1 (F): Interlacing polynomials
May 4 (M): Shearer Lemmar, number of graphs pairwise intersecting a triangle.
May 6 (W): Independence number of triangle-free graphs, points in space with all angles being acute.
May 7 (Th): Bounded degree tree embedding is sparse random graphs, dependent random choice