Math 595
Regularity Lemma and its applications

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

*****************************************************************************

  • Homework 1:  TBC (To Be Collected):
    Problem 1. Formulate and prove the counting lemma for the induced four-cycles, giving both lower and upper bounds.
    Problem 2. Prove the Slicing Lemma.
    Problem 3. Prove that when SZRL is applied to the half-graph, then there is always at least k non-\epsilon-regular pairs, where k is the number of partitions.
    Problem 4. Let $(V_1,V_2)$ be a bipartite graph with m edges, where m <= \epsilon^3|V1||V2|. Then this graph is epsilon-regular.
    Problem 5. For every $0 \le \epsilon, d \le 1$, every bipartite graph $B = (V_1\cup V_2,E)$ with $|V_1| = |V_2| = n$ and density $d$ contains an $\epsilon$-regular subgraph $B' = (U_1 \cup U_2,E)$ with density $d' \ge (1−\epsilon/3)d$ and $|U_1| = |U_2| \ge (n/2)*{d^{50/ epsilon^2}}$.
    Problem 6. Everything is about 3-uniform hypergraphs. Give good bounds on (1) f(n,7,4); (2) f(n,5,4); (3) f(n,5,3); (4) f(n,6,4); (5) f(n,6,6); (6) f(n,6,8); (7) f(n,6,9);                        DUE:  February 17 (Friday) 
                             
  • Homework 2:  TBC (To Be Collected):
    Problem 1. Prove that if the Hilbert cube B_d contains fewer than 2^d elements then it contains a 3-AP.
    Problem 2. Can you change in the proof of Schur general theorem the R(K_k,...K_k) to R(C_k,...,C_k)?
    Problem 3. Everything is about 3-uniform hypergraphs. Give good bounds on (1) f(n,6,6); (2) f(n,6,8); (3) f(n,6,9);
    Problem 4. Everything is about 3-uniform hypergraphs. Give good bounds on 1) f(n,7,4); (2) f(n,5,4); (3) f(n,5,3); (4) f(n,6,4)
    Problem 5. Give a rigorous proof of the theorem from Solymosi's lecture notes (i.e., if $|A+A|<|A|^ (1+c)$ then A contains a d-dimensional affine cube.)
    Problem 6. On Ramsey-Turan problems: Prove that f_3(n,K_6,o(n))<= n^2/6+o(n^2).
       DUE:  March 16 (Friday) 

  • Homework 3:  TBC (IF YOU HAVE UNEXCUSED ABSENCE, SUBMIT TYPED SOLUTION TO ALL PROBLEMS! (IF YOU ARE IN DOUBTS, THEN ASK!):
    Problem 1. Using Szemeredi-Trotter theorem, prove that n points in the plane determine at most $O(n^{7/3})$ triangles of unit area.
    Problem 2. Using Szemeredi-Trotter theorem, prove that n points in the plane determine at most $O(n^{7/3})$ triangles with a given fixed angle (say degree 38).
    Problem 3. Let Z_n be two-colored such that the number of numbers colored by blue is exactly a*n. Give lower and upper bound on the number of monochromatic AP-3's, in function of a and n.
    Problem 4. Recall the theorem in the class about RT(n,K_4, f(n))=o(n^2), where f(n) was some sublinear function. (in the topics of Ramsey-Turan questions.) State and prove a similar theorem about RT_3(n,K_5, f(n)) and RT_3(n,K_6, f(n)).
    Problem 5. Assume that you have a graph that every triangle has at most a common neighbors. Then prove the existence of a large spanning subgraph, whose average "triangle-degree" is low.
    Problem 6. Give a good bound on f(n,6,8) using the hypergraph dependent random choice lemma (not covered in the class).                        DUE:  May 4 (Friday noon, drop in mailbox or send via e-mail.)