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 **

- 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.

- Homework 1: TBC (To Be Collected): Ch 1: 1, 2, 3, 4, 5, 6; Ch 2: 1, 2.
DUE: September 14 (Wednesday)

- Homework 1: Do five of them: Ch 1: 1, 2, 3, 4, 5, 6; 7, 10;
DUE: February 16 (Monday)