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.