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: 10:00- 10:50 am MWF, 447 Altgeld Hall
Study session (in place of office hours): 1:00- 2:50 pm Illini Hall 7
MIDTERM: Time and place: Wed Nov 1
CANCELLED CLASSES: Nov 17 (F), Nov 27 (M)
MAKE UP CLASSES: Time and place: December 11 (M) and 13 (W), AH 343, 12:00-12:50
FALL 2017
- Homework 1: Do five of them: Ch 1: 1 -- 10;
DUE: September 18 (Monday)
- Homework 2: Do five of them: at least one from chapter 3:
Chapter 2: 1- 9;
Chapter 3: 2, 3;
DUE: October 2 (Monday)
- Homework 3: Do five of them: at least one from each chapter::
Chapter 4: 2, 3, 5;
Chapter 5: 1, 2, 3, 4, 5;
Chapter 6: 1, 2, 3;
DUE: October 18 (Wednesday)
- Homework 4: Do at least 5 problems!:
DUE: November 15 (Wednesday)
Do at least one from: Appendix: 1, 2;
Do at least one from: Chapter 9: 1, 2, 4;
Do at least one from (i) - (iv):
Problem (i): Show that for n sufficiently large there is a graph with n vertices, with chromatic number at least n/2 and
clique number at most n^{3/4}.
Problem (ii). Suppose that p=c/n, where c is fixed and n is sufficiently large (i.e. tending to infinity). (a) Prove
that w.h.p G(n,p) contains no set of vertices with s=|S|< n/(20 c^2) such that S contains (at least) 2s edges.
(b) Show that w.h.p. the maximum degree D<= ln n/ lnln n.
(c) Show that w.h.p. the vertices of degree at least 2 ln n/(3 lnln n) form an independent set.
Problem (iii): Consider the following random graph model on [n]: The probability of an edge in G is 1/2, independently
from all other edges, with not sharing an endpoint. [One possible model is: Let w: V -> [0,1], uniformly chosen random
function. uv is an edge iff w(u)+w(v)>1.].
(i) Using Second Moment Method, give good concentration result on e(G).
(ii) Using Chernoff's [think how to fight dependency], give good concentration result on e(G).
(iii) Where did you get better bound?
Problem (iv):
What is the precise threshold in G(n,p) for having minimum degree 2? (i.e. find f(n) such that if c(n)-> infty, and
p(n)=f(n)+c(n)/n, then whp the min. degree is at least 2, and if and p(n)=f(n)-c(n)/n, then whp the min. degree is less
than 2.
Chapter 15: 3, 4;
- Homework 5:
Do at least five problems [more will be added]:
DUE: December 6 (Wednesday)
1. (i) Give an Entropy proof of Hansen's inequality.
(ii) Strengthen it, when the union of the G_i's is F, whose independence number is at most a.
(iii) Strengthen it, assume that G_i's are k-partite, at least how many of them needed to cover K_n?
Chapter 7: 1 or 2 or 3 [do at least one but at most 2 from chapter 7].
Chapter 10: 1 or 2, [but not both]
Chapter 13: 1
Chapter 14: 1
Chapter 15: 3
Chapter 16: 1 or 2 [but not both]
SPRING 2015
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
- Homework 1: Do five of them: Ch 1: 1, 2, 3, 4, 5, 6; 7, 10;
DUE: February 16 (Monday)
- Homework 2: Do five of them: Ch 2: 1, 2, 3, 4, 5, 6; 7, 8, 9;
DUE: February 23 (Monday)
- Homework 3: Do five of them, at least one from each chapter: Ch 3: 1, 2, 3, 4; Ch 4: 2, 3, 5, 6; Ch 5: 1, 2, 3, 4, 5;
DUE: March 11 (Wednesday)
- Homework 4: Do five of them, at least one from each chapter: Ch 6: 1, 2, 3; Appendix: 1, 2; Ch 8: 1, 2; Problem #8: After Theorem 6.3.2. there is a displayed inequality, which might be not true, if A is a randomly chose l-set. Provide a (general) set up, where it is false, and prove it.
DUE: April 1 (Wednesday)
- Homework 5: (do 5 problems, at least 1 from chapter 7 and at least one from chapter 9)
Chapter 7: 1, 2, 3 nbsp;
Chapter 9: 9.1, 9.2.
Problem A: Show that for n sufficiently large there is a graph with n vertices, with chromatic number at least n/2 and clique number at most n^{3/4}.
Problem B. Suppose that p=c/n, where c is fixed and n is sufficiently large (i.e. tending to infinity).
(a) Prove that w.h.p G(n,p) contains no set of vertices with s=|S|< n/(20 c^2)
such that S contains (at least) 2s edges.
(b) Show that w.h.p. the maximum degree D<= ln n/ lnln n.
(c) Show that w.h.p. the vertices of degree at least 2 ln n/(3 lnln n) form an independent set.
Problem C: Consider the following random graph model on [n]: The probability of an edge in G is 1/2, independently from all other edges, with not sharing an endpoint.
[One possible model is: Let w: V -> [0,1], uniformly chosen random function.
uv is an edge iff w(u)+w(v)>1.].
(i) Using Second Moment Method, give good concentration result on e(G).
(ii) Using Chernoff's [think how to fight dependency], give good concentration result on e(G).
(iii) Where did you get better bound?
DUE: April 27 (Monday)
- Homework 6: do 5 problems:
Chapter 9: 9.3, 9.4;
Chapter 10: 10.1, 10.2 (needs to have a self-complete proof! ask if in doubt!)
Chapter 14: 14.2, 14.3 (entropy section!!!);
Chapter 13: 13.1 (there are n points in the plane, discrepancy of shapes covered by a triangle!)
Chapter 12: 1, 3 (discrepancy section)
Problem A. What is the precise threshold in G(n,p) for having minimum degree 2? (i.e. find f(n) such that if c(n)-> infty, and p(n)=f(n)+c(n)/n, then whp the min. degree is at least 2, and if and p(n)=f(n)-c(n)/n, then whp the min. degree is less than 2.
Problem B: Let A be collection of points in the n-dimensional Hamming ball, having at most k 1 coordinates. What is the set of points, which are within distance t of A?
Problem C: Prove that if a discrete random variable X satisfies that for every s, P(X=s) < 2^{-t} then H(X)> t.
DUE: May 13 (Wednesday)
*****************************************************************************
EVERYTHING BELOW IS FROM 3 YEARS AGO!!!!
*****************************************************************************
TEST is NOVEMBER 1, 6:00-7:30pm
*****************************************************************************
Math majors should do from each assignment 5 problems, non-math majors 4 problems.
The problems are from Alon-Spencer: Probabilistic methods 3rd edition
- Homework 1: TBC (To Be Collected): Ch 1: 1, 2, 3, 4, 5, 6; Ch 2: 1, 2.
DUE: September 14 (Wednesday)
- Homework 2: TBC (To Be Collected): Ch 2: 5, 7, 9; Ch 3: 2, 3;
Ch 4: 1, 2, 3, 4, 5;
DUE: September 26 (Monday)
- Homework 3: TBC (To Be Collected):
Ch 1: 7, 8; Ch 5: 3, 4; Ch 6: 1, 2, 3;
Problem 8. What bound can you obtain for R(k,5) using the E. L. Local Lemma?
DUE: October 10 (Monday)
- Homework 4: TBC (To Be Collected):
Ch 4: 2, 3, 5; (only if you have not submitted solution for them in HW2); Ch 8: 1, 2;
Problem A. What is the precise threshold in G(n,p) for having minimum degree 2? (i.e. find f(n) such that if c(n)-> infty, and p(n)=f(n)+c(n)/n, then whp the min. degree is at least 2, and if and p(n)=f(n)-c(n)/n, then whp the min. degree is less than 2.
Problem B. Provide a proof of Theorem 8.3.1. for t>0.
Problem C: Consider the following random graph model on [n]: The probability of an edge in G is 1/2, independently from all other edges, with not sharing an endpoint.
[One possible model is: Let w: V -> [0,1], uniformly chosen random function.
uv is an edge iff w(u)+w(v)>1.].
(i) Using Second Moment Method, give good concentration result on e(G).
(ii) Using Chernoff's [think how to fight dependency], give good concentration result on e(G).
(iii) Where did you get better bound?
DUE: October 29 (Friday)
- Homework 5: TBC (To Be Collected):
Chapter A: 1, 2, 5; Chapter 7: 1, 2, 3
Problem A: Show that for n sufficiently large there is a graph with n vertices, with chromatic number at least n/2 and clique number at most n^{3/4}.
Problem B. Suppose that p=c/n, where c is fixed and n is sufficiently large (i.e. tending to infinity).
(a) Prove that w.h.p G(n,p) contains no set of vertices with s=|S|< n/(20 c^2) such that S contains (at least) 2s edges.br>
(b) Show that w.h.p. the maximum degree D<= ln n/ lnln n.
(c) Show that w.h.p. the vertices of degree at least 2 ln n/(3 lnln n) form an independent set.
DUE: November 14 (Monday)
- Homework 6: TBC (To Be Collected):
Chapter 9: Do two out of 9.1, 9.2, 9.3, 9.4;
Chapter 10: 10.1, 10.2 (needs to have a sef-complete proof! ask if in doubt!)
Chapter 14: 14.1;
Chapter 15: 15.2, 15.3;
DUE: December 7 (Wednesday)
Class Announcements
TEST is NOVEMBER 1, 6:00-7:30pm, Location: AH 141
Last changed on December 17, 2011.