Problem Set 1

1. (Just checking you can use Cauchy-Schwarz) Suppose that S and T are nonempty finite sets and ρ a map from S to T show that

∑ t

|ρ−1(t)|2 ≥ |S| 2

|T | .

(This was the final step in my proof of the combinatorial Cauchy-Schwarz inequality that I left to you.)

 

2. (Applying Balog-Szemeredi-Gowers 1) Suppose that A is a nonempty finite subset of an abelian group Z. Suppose that E(A) = 1

K . Show that there is a constant C independent of K so that there exist sets A1, A2 ⊂ A with

|A1| > |A| CK

,

|A2| > |A| CK

and |A1 +A2| ≤ CK8|A|.

(I basically indicated how you can do this in lecture.)

 

3. (Applying Balog-Szemeredi-Gowers 2) With the same hypotheses as problem 2, show there is a constant C independent of K (but maybe dependent on the base of log that appears in this problem) and A1, A2 ⊂ A with

|A1| > |A|

CK(1 + logK) ,

|A2| > |A|

CK(1 + logK) ,

and |A1 +A2| < CK3(1 + logK)5|A|.

Hint: When choosing G, sort together those pairs whose sums have approximately the same number of representations. If you get a different upper bound than I did, it could mean that I screwed up this problem. In that case, prove the best upper bound you can.

 

4. (Applying Balog-Szemeredi-Gowers 3) In both problems 2 and 3, you are given an upper bound for |A1 +A2|. Can you get a reasonable upper bound for |A1 +A1|. An upper bound is reasonable if it is a constant times a power of K times a power of (1 + logK) so for example, the upper bounds you got for |A1 +A2| in problems 2 and 3 were reasonable.

1

 

 

C

 

5. (This is problem 6.4.3 from Tao-Vu.) Let G = G(A, B, E) be a bipartite graph. Here A

and B are the parts and E is the set of edges, which we’ve been calling G. Here let |A| = |B| = N with N sufficiently large. Show that there is a function f from (1, ∞) to

2

(1, ∞) so that if |E| > N then G contains a complete bipartite subgraph with at least f(C) logN vertices in each part. Show that logN is the optimal dependence in N for such a result.

2