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.
