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

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

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)

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)

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